Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 1.0 Seconds Memory Limit: 65536K

Total Runs: 752 Accepted Runs: 284

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.### Input

There are several test cases in the input.### Output

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.### Sample Input

### Sample Output

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?

The first line of each test case contain two integers *N* and *M* (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* and *B*, indicating there is a branch between *A* and *B*. (1 ≤ *A*,*B* ≤ 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* = *M* = 0.
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.

3 2 1 2 2 3 100 10 -20 3 3 1 2 2 3 1 3 100 100 100 0 0

-10 No apple

**Problem Setter:** RoBa

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz