It is a well known fact that Sam is USACO Platinum. After his atrocious performance on the CCC, however, Bruce is beginning to have doubts.
To test his suspicions, Bruce kidnaps Sam right before class and drops him off in a faraway island of connected islands, joined by bidirectional bridges. However, the bridges are brittle, so bridge can only be traversed a maximum of times. Moreover, the of the islands houses a treasure chest of value .
Right before Bruce leaves to teach Sam's class without him, he tells Sam that he has one chance to tell him the maximum value of treasure chests he can obtain. If he fails to do so, Bruce will leave Sam stranded on the island forever, a grave punishment for lying about his USACO status. However, Sam, who is really USACO Silver, is unable to solve this problem. He passes it on to Daniel, who passes it on to you to solve!
Give that Sam starts at island and can end at any island, help Daniel find the right answer for Sam!
For all subtasks:
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
The first line of input will contain the integer , the number of islands.
The second line of input will contain positive integers .
The next lines will contain , , and , representing a bidirectional edge between and that can be traversed a maximum of times.
Output one integer representing the maximum amount of treasure Sam can gather. Please note that 64-bit integers may be required for full marks.
Sample Input 1
3 4 8 5 1 2 2 2 3 2
Sample Output 1
Explanation for Sample Output 1
Sam's optimal path is , gathering units of treasure. Note that Sam is able to return to his starting position, but this is not required for this case.
Sample Input 2
5 8 10 4 9 1 1 2 1 1 3 2 2 4 1 2 5 1
Sample Output 2
Explanation for Sample Output 2
Sam's optimal path is , gathering units of treasure. Note that since each treasure chest can only be retrieved once, returning to island doesn't grant additional treasure.