I. Fishing deal with ziplines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

High above the valleys, the legendary Mount Thalassa feeds a vast river system. From a single source at the summit, the river splits into smaller and smaller streams, forming a tree-like structure flowing down the mountain.

Along these waterways lie isolated fishing spots. The fishing spots correspond exactly to the nodes of this tree. Each spot produces a fixed amount of fish every year. Because of the rugged terrain, these locations are difficult to access, and the transport infrastructure is limited to what was built long ago: downstream rails that allow fish to be transported downriver, and ziplines that allow fish to be transported upriver.

Each transport connection has a maximum yearly capacity.

Two rival companies, AquaDyn Fisheries and BlueCurrent Co., have been instructed to split the mountain's fishing resources evenly.

They agree on the following:

  • Every fishing spot must belong to exactly one company.
  • The fishing spots owned by each company must form a connected component of the tree.
  • Each company will ensure it can collect fish from its own fishing spots to its warehouses, but will not build new infrastructure to redistribute fish between spots.
  • Any transfer of fish between the two companies must rely solely on the existing transport network.

Fishing spots produce a fixed amount of fish, but they can store and handle any amount of incoming fish.

After choosing a valid repartition of the fishing spots, the two companies compare the total yearly fish production of their respective regions.

  • If both sides already have the same total, the agreement is immediate.
  • Otherwise, fish must be transferred from one side to the other using the existing network.

Your task is to determine a valid repartition of the fishing spots so that the two companies can end up with equal total amounts of fish, while minimizing the amount of fish that needs to be transferred between them. The transfer can only be done on integer quantities.

If multiple choices are possible, any one minimizing the required transfer is acceptable.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of fishing spots.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i \le 10^9$$$ is the yearly fish production of spot $$$i$$$.

The following $$$n-1$$$ lines describe the transport network. Each line contains four integers: $$$u \ v \ c_{uv} \ c_{vu}$$$

  • $$$u$$$ and $$$v$$$ are connected fishing spots
  • $$$c_{uv} \le 10^9$$$ is the capacity for transporting fish from $$$u$$$ to $$$v$$$
  • $$$c_{vu} \le 10^9$$$ is the capacity for transporting fish from $$$v$$$ to $$$u$$$

It is guaranteed that the graph formed by the fishing spots and connections is a tree.

Output

Output a single integer — the minimum amount of fish that must be transferred between the two companies after choosing an optimal repartition.

If it is impossible to balance the total amount of fish for any valid repartition, output $$$-1$$$.

Examples
Input
2
3 3
1 2 0 0
Output
0
Input
2
1 9
1 2 5 0
Output
-1
Input
2
1 9
1 2 0 5
Output
4
Note
  • Fish can be transported along multiple edges, respecting capacities and directions.
  • Fishing spots do not produce additional fish beyond their initial value.
  • Fishing spots can store arbitrarily large amounts of fish.
  • Every fishing spot must belong to exactly one of the two connected components.
  • No new transport connections can be added.