Hospitals

There are N villages numbered from 1 to N, connected by a road network. In this network, there is exactly one path between any two villages. You are given the population of each village and the travel time of each road. Exactly two distinct villages have hospitals.

The time needed to travel from village A to village B is the sum of the travel times of the roads on the unique path between them.

Consider the road network shown below.

Figure 1

Each circle represents a village. The number inside a circle is the village number, and the number outside it is the population of that village. Each line segment is a road, and the number on it is the road's travel time. The two villages with hospitals are shaded gray.

You may spend a budget on road improvements to reduce road travel times. Spending budget C on a road reduces that road's travel time by C. The total budget B may be spent subject to the following conditions.

Conditions

1. No matter how much budget is spent on a road, its travel time cannot become less than L.
2. The total budget spent on road improvements must be at most B.

The values L and B are given in the input.

Subject to these conditions, compute the following two values.

• Question 1: Minimize the sum, over all people, of the time needed for each person to reach the closer hospital. What is the minimum possible sum?
• Question 2: Minimize the maximum, over all people, of the time needed for each person to reach the closer hospital. What is the minimum possible maximum time?

In Figure 1, if the total budget is B = 7 and L = 6, one optimum for Question 1 spends budget 3 on road (1, 3), budget 1 on road (2, 3), and budget 3 on road (5, 7), making their travel times 6, 7, and 6. Then the total time for all people to reach a hospital is 50×6 + 20×7 + 10×5 + 20×5 + 30×6 + 15×7 = 875.

For Question 2, spending budget 2 on each of roads (1, 3), (4, 5), and (5, 7), and budget 1 on road (2, 3), makes the longest time from any person to the closer hospital equal to 7.

No allocation of the budget can improve either of these two values.

The first line contains two positive integers B and L: the total budget and the lower bound on a road's travel time. 1 ≤ B ≤ 4,000,000 and 1 ≤ L ≤ 1,000.

The second line contains the number of villages N. 2 ≤ N ≤ 4,000.

The third line contains the populations of villages 1 through N in order. Each population is between 1 and 500, inclusive.

Each of the next N - 1 lines contains information about one road: the two endpoint village numbers and the road's travel time, separated by spaces. Each travel time is between 1 and 1,000, inclusive.

The last line contains the numbers of the two distinct villages that have hospitals.

Print the answer to Question 1 on the first line.

Print the answer to Question 2 on the second line.

Note that an answer may exceed 2^32.