There is an apple tree in Robby's yard, and there are many apples on it. For simplicity, we consider the tree as a graph, the nodes indicating the root of the apple tree and the positions where the apples grow, and the edges indicating the branches of the tree. Robby gives each apple a delicious value, for example, the apple with value 1 tastes a little well, while the apple with value -100 tastes terrible.
Now Robby wants to cut a branch and eat all the apples fallen off - If an apple is not connected to the root by branches, it will fall off. Please note, you know, Robby is a strange person, so his apple tree is not a normal tree too. That is, not every cut can cause some apples to fall.
Robby wants the sum of the fallen apples' delicious value as much as possible. Can you help him?
There are several test cases in the input.
The first line of each test case contain two integers N
(1 ≤ N ≤ 10000, 1 ≤ M
≤ 100000) indicating the number of nodes (including the root) and the number of branches. Then M
lines follow, each line contain two numbers A
, indicating there is a branch between A
. (1 ≤ A
≤ N, A ≠ B) The last line of each test case contain N
numbers, indicating the delicious value of apples on each node. The delicious value of each apple is between -100 and 100.
The input terminated with N
All the nodes are numbered from 1 to N
. The root is always node 1. There is at most one edge between any pair of nodes. And the graph is guaranteed to be connected.
Output one line for each test case, indicating the maximum total delicious value of the apples fallen off after one cut, or "No apple" if Robby can't get any apples.
100 10 -20
100 100 100