You are a forest ranger who has been given a task: plant trees on plots of land in a forest and nurture them until they reach a specified height.

The forest map consists of $n$ plots, where plot 1 is connected to the forest entrance. There are $n - 1$ roads connecting these plots such that every plot is reachable from any other plot. Initially, there are no trees on any of the plots.

Your goal is to plant one tree on each plot such that the tree on plot $i$ grows to a height of at least $a_i$ meters.

Each day, you can choose a plot that does not yet have a tree and is directly adjacent (connected by a single road) to a plot that already has a tree, and plant a tree with an initial height of 0 meters. If all plots already have trees, you do not perform any operations that day. Specifically, on day 1, you can only plant a tree on plot 1.

For each plot, starting from the day the tree is planted, the tree on that plot grows by a certain height each day. Due to different climate and soil conditions, on day $x$, the tree on plot $i$ will grow by $\max(b_i + x \times c_i, 1)$ meters. Note that $x$ is calculated from the first day of the entire task, not from the day the tree was planted.

You want to know: what is the minimum number of days required to complete your task?

Input

The first line contains a positive integer $n$, representing the number of plots in the forest.

The next $n$ lines each contain three integers $a_i, b_i, c_i$, describing each plot as mentioned in the problem description.

The next $n - 1$ lines each contain two positive integers $u_i, v_i$, representing a road connecting plots $u_i$ and $v_i$.

Output

Output a single line containing a positive integer, representing the minimum number of days required to complete the task.

Examples

Input 1

4
12 1 1
2 4 -1
10 3 0
7 10 -2
1 2
1 3
3 4

Output 1

5

Note 1

Day 1: Plant a tree on plot 1. The tree on plot 1 grows to 2 meters. Day 2: Plant a tree on plot 3. The trees on plots 1 and 3 grow to 5 and 3 meters, respectively. Day 3: Plant a tree on plot 4. The trees on plots 1, 3, and 4 grow to 9, 6, and 4 meters, respectively. Day 4: Plant a tree on plot 2. The trees on plots 1, 2, 3, and 4 grow to 14, 1, 9, and 6 meters, respectively. Day 5: The trees on plots 1, 2, 3, and 4 grow to 20, 2, 12, and 7 meters, respectively.

Examples 2-4

See the files tree/tree2.in and tree/tree2.ans, tree/tree3.in and tree/tree3.ans, and tree/tree4.in and tree/tree4.ans in the contestant directory.

Constraints

For all test data: $1 \le n \le 10^5$, $1 \le a_i \le 10^{18}$, $1 \le b_i \le 10^9$, $0 \le |c_i| \le 10^9$, $1 \le u_i, v_i \le n$. It is guaranteed that a solution exists within $10^9$ days.

Special Property A: For all $1 \le i \le n$, $c_i = 0$. Special Property B: For all $1 \le i < n$, $u_i = i, v_i = i + 1$. Special Property C: No plot is connected to more than 2 roads. Special Property D: For all $1 \le i < n$, $u_i = 1$.