병원

1번부터 N번까지 번호가 붙은 N개의 마을이 도로망으로 연결되어 있다. 이 도로망에서는 어떤 마을에서 다른 마을로 가는 경로가 항상 정확히 하나뿐이다. 각 마을의 인구와 각 도로를 지나가는 데 걸리는 시간이 주어진다. 또한 서로 다른 두 마을에는 병원이 하나씩 있다.

마을 A에서 마을 B까지 가는 데 걸리는 시간은 두 마을을 잇는 유일한 경로에 포함된 도로들의 통행 시간의 합이다.

다음 그림과 같은 도로망을 생각해 보자.

그림 1

동그라미는 마을을 나타낸다. 동그라미 안의 수는 마을 번호이고, 바깥의 수는 그 마을에 사는 사람 수이다. 선분은 도로를 나타내며, 선분 위의 수는 그 도로의 통행 시간이다. 병원이 있는 두 마을은 회색으로 표시되어 있다.

예산을 도로 개선에 사용하면 도로의 통행 시간을 줄일 수 있다. 어떤 도로에 예산 C를 사용하면 그 도로의 통행 시간이 C만큼 줄어든다. 전체 예산 B를 다음 조건을 만족하도록 도로 개선에 사용할 수 있다.

조건

1. 어떤 도로에 예산을 많이 쓰더라도 그 도로의 통행 시간을 L보다 작게 만들 수는 없다.
2. 도로 개선에 사용한 예산의 총합은 B 이하여야 한다.

L과 B는 입력으로 주어진다.

위 조건을 만족하도록 예산을 사용할 때, 다음 두 값을 구하시오.

• 질문 1: 각 사람이 더 가까운 병원까지 가는 데 걸리는 시간의 합을 최소로 만들 때, 그 합의 최솟값은 얼마인가?
• 질문 2: 각 사람이 더 가까운 병원까지 가는 데 걸리는 시간 중 최댓값을 최소로 만들 때, 그 최소 가능한 최댓값은 얼마인가?

그림 1에서 전체 예산이 B = 7이고 L = 6이면, 질문 1에서는 도로 (1, 3)에 예산 3, 도로 (2, 3)에 예산 1, 도로 (5, 7)에 예산 3을 사용하여 통행 시간을 각각 6, 7, 6으로 만들 수 있다. 이때 모든 사람이 병원까지 이동하는 시간의 합은 50×6 + 20×7 + 10×5 + 20×5 + 30×6 + 15×7 = 875이다.

질문 2에서는 도로 (1, 3), (4, 5), (5, 7)에 각각 예산 2를 사용하고 도로 (2, 3)에 예산 1을 사용하면, 각 사람이 더 가까운 병원까지 가는 데 걸리는 시간 중 최댓값이 7이 된다.

어떤 방식으로 예산을 사용해도 위 두 값보다 더 좋게 만들 수 없다.

첫째 줄에 전체 예산 B와 하한 시간 L을 나타내는 두 양의 정수가 공백으로 구분되어 주어진다. 1 ≤ B ≤ 4,000,000, 1 ≤ L ≤ 1,000이다.

둘째 줄에 마을의 수 N이 주어진다. 2 ≤ N ≤ 4,000이다.

셋째 줄에는 1번 마을부터 N번 마을까지 각 마을에 사는 사람 수가 차례대로 주어진다. 각 값은 1 이상 500 이하이다.

다음 N - 1개 줄에는 도로의 정보가 주어진다. 각 줄에는 도로가 잇는 두 마을의 번호와 그 도로의 통행 시간이 공백으로 구분되어 주어진다. 통행 시간은 1 이상 1,000 이하이다.

마지막 줄에는 병원이 있는 서로 다른 두 마을의 번호가 공백으로 구분되어 주어진다.

첫째 줄에 질문 1의 답을 출력한다.

둘째 줄에 질문 2의 답을 출력한다.

답이 2^32를 넘을 수 있음에 유의하라.