Bob's English class has been given a project which must be done in pairs. The class size, , is even. Each pair needs to meet outside class to do the project.
The city which Bob and his classmates live in is a tree. It has zones labelled
. There are
roads so that one can travel from any zone to any other. The
road connects zones
and
and has distance
.
The student lives in zone
. Bob defines the cost of a pair to be the distance between the zones of the two students in the pair. Bob is wondering what the total of the
costs is. Since the pairs haven't been assigned yet, he wants to know the worst-case. That is, what is the maximum possible total of the costs?
Constraints
is even
Subtask 1 [10%]
for all
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [40%]
Input Specification
The first line contains two space-separated integers, and
.
The next line contains space-separated integers,
.
The next lines each contain three space-separated integers,
, the description of
road.
Output Specification
Output a single integer, the maximum possible total.
Sample Input 1
8 4
2 2 2 2 1 2 2 2
1 2 7
1 3 3
1 4 1
Sample Output 1
7
Explanation for Sample 1
The pairs of students give costs
. The total is
which is the maximum possible.
Sample Input 2
8 8
1 2 3 4 5 6 7 8
1 4 2
2 4 7
3 4 7
4 5 1
5 6 2
6 7 3
7 8 4
Sample Output 2
36
Explanation for Sample 2
The pairs of students give costs
. The total is
which is the maximum possible.
Sample Input 3
10 5
1 1 1 1 1 5 5 5 5 5
1 2 1
2 3 1
3 4 1
4 5 1
Sample Output 3
20
Explanation for Sample 3
The pairs of students give costs
. The total is
which is the maximum possible.
Comments