시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 28 5 5 41.667%

문제

이 나라의 교통망은 N개의 도시로 이루어져 있으며(1~N의 정수로 번호가 매겨져 있다) N-1개의 도로가 도시들을 연결한다. 서로 다른 두 도시 간에는 특별한 경로가 존재한다.

수년간의 게으른 도로 보수로 인해 도로는 꽤 손상되었고 각각의 도로는 A와 B의 숫자를 가지고 있다. 정수 A는 현재 해당 도로를 통해서 이동할 때 걸리는 시간을 나타내며, 정수 B는 만일 모든 도로를 복구해 놓았을 경우, 이 도로를 통해서 이동할 때 걸리는 최소 시간(초 단위)을 나타낸다.

도로를 복구하는 데에 일정 금액의 비용을 투자할 것이다. 특정 도로는 투자한 비용에 비례하여 그 결과가 나타날 것이다. 각 금액(유로)은 몇몇 도로에 투자될 것이며, 도로를 따라 이동하는데 걸리는 시간은 매 순간 감소할 것이다(도로에 투자하는 비용은 정수이다). 이동 소요 시간은 가능한 최솟값인 B보다 작아질 수 없다.

일정 금액의 돈이 주어지면, 이 돈을 '도시 1'에서부터 가장 먼 도시까지 걸리는 이동 소요시간(모든 복구 작업이 끝난 후)이 최소한이 되는 방법으로 도로에 분배하고 싶다.

입력

첫째 줄에 도시의 개수 N과 총 금액 K(유로)가 주어진다. (2 ≤ N ≤ 100 000, 0 ≤ K ≤ 1 000 000)

둘째 줄부터 N-1개의 줄에 4개의 정수 X, Y, A, B가 주어진다. 이는 도시X와 도시Y 사이에 도로가 있으며, 현재 소요시간 A과 문제에서 언급한 최소 시간 B를 나타낸다. (0 ≤ B ≤ A ≤ 10 000)

출력

최소 시간을 출력한다.

예제 입력

3 200
1 2 200 100
2 3 450 250

예제 출력

450

힌트