시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 35 | 26 | 22 | 70.968% |
In the Republic of JOI, there are N cities numbered from 1 to N. The cities are connected with N − 1 roads. People in the Republic of JOI are travelling between cities using these roads. They can pass each of the roads in both directions. They can travel between any two cities by passing through one or several roads.
Mr. IOI is a candidate for the president of the Republic of JOI. Of course, to become the president, he must perform the campaign for the presidential election. His secretary made M plans for the election campaign. In the i-th plan, Mr. IOI will travel from the city Ai to the city Bi passing through minimum number of roads, and make a public speech in each of the cities on the way (including the city Ai and the city Bi). Because his secretary is brilliant, it is known that Mr. IOI will get Ci votes if the i-th plan is performed. It is possible to perform several plans.
However, people in the Republic of JOI are impatient. If Mr. IOI makes public speeches more than once in the same city, he will lose the support from people in the Republic of JOI.
Because Mr. IOI would like to become the president, he wants to get as many votes as possible. Since you are a superprogrammer in the Republic of JOI, he asked you to write a program which calculates the maximum number of votes Mr. IOI can get in the presidential election under the assumption that he will not make public speeches more than once in the same city.
Given the number N of cities in the Republic of JOI, the information on the roads, the number M of plans for the election campaign, and information of each plan, write a program which calculates the maximum number of votes Mr. IOI can get in the presidential election.
Read the following data from the standard input.
The output should consist of one line, and contain one integer which denotes the maximum number of votes Mr. IOI can get in the presidential election.
All input data satisfy the following conditions.
There are no additional constraints.
7 3 4 6 5 2 7 1 5 7 5 4 5 5 4 3 10 5 6 5 2 6 9 7 2 2 1 3 8
19
In this sample input, the optimal strategy is to perform the plan 1 and the plan 3 for the election campaign.
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 5 7 5 4 5 8 9 4 3 9 1 3 3 2 8 11
18
This sample input satisfies the constraints of the subtask 3.
10 10 6 2 7 1 9 9 8 3 8 6 4 7 8 5 4 4 8 7 1 3 1 4 10 1 2 8 1 5 3 1 3 7 1 8 5 1 1 9 1
3
This sample input satisfies the constraints of the subtask 4.
20 17 10 11 4 8 3 3 16 1 14 15 18 5 4 6 18 10 18 19 4 16 7 2 13 4 12 12 20 9 20 18 13 20 14 14 7 13 7 15 19 9 2341 13 8 6974 8 3 3339 15 17 6515 10 13 4370 1 7 8376 18 2 9272 6 7 4595 1 20 505 10 9 308 6 19 8937 2 15 5072 5 4 4217 2 4 4170 19 12 8204
29191