A salesman, Little T, needs to travel to several towns to promote products. Because the region is a mountainous area with poor transportation, there is a unique path between any two towns that does not pass through other towns. Little T can accurately estimate the net profit of staying in each town. These net profits may be negative, meaning the profit from promoting products does not cover the expenses. Due to the poor transportation, Little T must stay in every town he passes through. The number of stays in each town is independent of the net profit at that location, as many costs are not charged per visit, and the demand for Little T's products in each town is relatively fixed; it becomes saturated after one stay. To strengthen security, each town has strict regulations on the maximum number of stays for outsiders. Please help Little T design a tour plan with maximum profit, starting from his hometown, staying in every town he passes through, and finally returning to his hometown. Your program only needs to output the maximum profit and whether the optimal plan is unique. The plan does not include the details of the route; the criterion for the same plan is whether the set of towns visited and stayed in is the same. Since canceling the tour is also a plan, the maximum profit will not be negative. Little T's net profit in his hometown is zero because he is a local, and naturally, there is no limit on the number of stays in his hometown.

Input

The first line of the input is a positive integer $n$, representing the number of towns. The towns are named from $1$ to $n$. Little T's hometown is named $1$. The second and third lines both contain $n-1$ space-separated integers. The $i$-th number in the second line represents the net profit of staying in town $i+1$. The $i$-th number in the third line represents the maximum number of stays allowed in town $i+1$. All maximum stay limits are no less than $2$. The following $n-1$ lines each contain two positive integers $x$ and $y$ between $1$ and $n$, separated by a space, indicating that there is a bidirectional road between $x$ and $y$ that does not pass through other towns. The input data guarantees that all towns are connected.

Output

The output consists of two lines. The first line contains a natural number representing the maximum profit of the tour. If the plan is unique, output "solution is unique" on the second line; otherwise, output "solution is not unique".

Examples

Input 1

9
-3 -4 2 4 -2 3 4 6
4 4 2 2 2 2 2 2 
1 2 
1 3
1 4
2 5
2 6
3 7
4 8 
4 9

Output 1

9
solution is unique

Note 1

The optimal route includes towns $1, 2, 4, 5, 9$.

Constraints

All net profits are between $-500$ and $500$, and all maximum stay limits are no greater than $1000$.

• $30\%$ of the data satisfies: $5 \le n \le 10$
• $60\%$ of the data satisfies: $5 \le n \le 1000$
• $100\%$ of the data satisfies: $5 \le n \le 100000$