Magical Potion Preparation

Chemist Jill wants to prepare a magical potion to save the world. She has n different liquid substances and n bottles, numbered from 1 to n. Initially, the i-th bottle contains \(g_i\) grams of the i-th substance.

Jill will perform exactly n - 1 pouring steps. In the i-th step, she pours all the liquid from bottle \(a_i\) into bottle \(b_i\); after that, bottle \(a_i\) will no longer be used. Bottles have infinite capacity.

Furthermore, certain pairs of substances react when mixed: specifically, \(1\) gram of substance \(c_i\) and \(1\) gram of substance \(d_i\) will react to produce \(2\) grams of precipitate. This reaction continues until one of the reactants is exhausted, and the precipitate does not react further.

If more than one reactive pair is present after a pour, the reactions occur sequentially in a predetermined order (the same order as provided in the input). Jill waits for the reaction(s) to finish after each pouring step before proceeding to the next.

Your task is to determine the total amount of precipitate produced during the entire process.

inputFormat

The first line contains two integers (n) and (r), where (n) is the number of substances (and bottles) and (r) is the number of reactive pairs. The second line contains (n) integers: (g_1, g_2, \dots, g_n), representing the initial grams in each corresponding bottle. Each of the next (n-1) lines contains two integers (a_i) and (b_i), indicating that in the (i)-th step, all liquid from bottle (a_i) is poured into bottle (b_i). Each of the next (r) lines contains two integers (c_i) and (d_i), denoting that substance (c_i) reacts with substance (d_i) according to the rule described above.

outputFormat

Output a single integer representing the total grams of precipitate produced.

sample

3 1
5 3 4
1 2
2 3
1 2

6