Global Conquest Logistics

Your nemesis, the charming spy Waco Powers, has been neutralized, and now it is time to execute your master plan: CONQUER THE WORLD! However, a serious logistical issue stands in your way. Your evil armies, the backbone of your impending world domination, demand proper payment and deployment. Unfortunately, your funds are tight, and you must move your armies across the nations as cheaply as possible.

You are given a map of the world represented as n nations connected by transport routes. These routes form a tree (i.e. there is exactly one unique path between any two nations). Each route connects two nations and has a fixed cost per army that uses it.

Each nation i has an initial number of armies a_i and requires a specific number of armies r_i to be permanently stationed for subjugation. It is guaranteed that the sum of all initial armies equals the sum of all required armies so that a solution always exists.

Your task is to move the armies between nations so that every nation ends up with exactly the required number of armies, while minimizing the total transport cost. When an army is moved along a route with cost w, the cost incurred is w per army. Use the formula below for each route:

where flow is the net number of armies moved through that route. Compute and output the minimal total cost required to achieve the desired configuration.

inputFormat

The input is given as follows:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nations.
• The second line contains n integers a1, a2, ..., an representing the initial number of armies at each nation.
• The third line contains n integers r1, r2, ..., rn representing the required number of armies for each nation.
• The next n-1 lines each contain three integers u v w denoting a transport route between nations u and v with a cost w per army.

outputFormat

Output a single integer: the minimal total cost to move the armies so that every nation gets exactly the required number of armies.

sample

3
1 0 2
0 2 1
1 2 3
2 3 4

7