You are given a tree consisting of ~N~ nodes and ~N-1~ edges. Each edge has a weight ~w_i~ and each node as a value ~v_i~. You can perform the following two operations on the tree any number of times:

• Double a node ~u~'s value. In other words, ~v_u = v_u \times 2~.
• Take an edge ~k~ and divide (integer division) the edge's weight by the GCD (greatest common divisor) of the value of the nodes connected by the edge. In other words, ~w_k = \bigg\lfloor \frac{w_k}{GCD(a_k, b_k)} \bigg\rfloor~, where ~a_k~ and ~b_k~ are the two nodes the edge connects.

After performing the above two operations any number of times, what is the minimum sum of all the edge weights and node values?

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~.

The next line will contain ~N~ integers, ~v_i~ ~(1 \le v_i \le 10^9)~.

The next ~N-1~ lines will each contain three integers, ~a_j, b_j, w_j~ ~(1 \le a_j, b_j \le N, 1 \le w_j \le 10^9)~, meaning that nodes ~a_j~ and ~b_j~ will be connected by an edge of weight ~w_j~. It is guaranteed that the tree will be fully connnected.

Output Specification

Output the minimum sum of all the edge weights and node values after performing the above operations any number of times.

Sample Input

3
3 2 1
1 2 10
2 3 9

Sample Output

10