Turtle Elder

Interview

Time limit5sMemory limit256 MB

Summary

Pick safe start and end islands in a tree so the sum of values along the path is as large as possible, staying home when the best sum is not positive.

Level: Medium4 of 10
Topics: Tree, Dynamic programming
Solved: No attempts yet

Problem

N islands form a tree. Touching island i changes lifespan by $X_i$ days. Some islands are unsafe for landing or signaling. With only one flare, choose safe entry and exit islands to maximize lifespan gain. If the best gain is not positive, print Stay Home.

Input

The first line contains $T$ test cases ( $T \le 10$ ). Each test case gives $N$ , $N-1$ bridges, array $X_i$ , and a safe/island mask.

Output

Print the maximum lifespan gain, or Stay Home if it is not positive.

Examples1

Example 1

Input

2
3
1 2
2 3
5 20 -10
1 0 1
4
1 2
2 3
3 4
-1 5 -20 -1
1 0 0 1

Expected output

15
Stay Home