도로 보수
시간 제한2초메모리 제한128 MB
트리 형태 도로망에서 각 도로의 이동 시간을 예산 한도 내에서 줄여, 도시 1에서 가장 먼 도시까지의 최단 이동 시간을 최소화하는 문제입니다.
문제
어떤 나라의 교통망은 1번부터 N번까지 번호가 붙은 도시 N개와 도시들을 잇는 도로 N - 1개로 이루어져 있다. 서로 다른 두 도시 사이에는 항상 정확히 하나의 경로가 있다.
도로는 오랫동안 제대로 관리되지 않아 많이 손상되었다. 각 도로에는 두 정수 A와 B가 주어진다. A는 현재 그 도로를 지나는 데 필요한 시간(초)이고, B는 그 도로를 완전히 보수했을 때 가능한 최소 시간(초)이다.
도로 보수에는 일정한 예산을 사용할 수 있다. 한 도로에 1유로를 투자할 때마다 그 도로의 이동 시간이 1초 줄어든다. 각 도로에 투자하는 금액은 정수여야 하며, 도로의 이동 시간은 최소값 B보다 작아질 수 없다.
주어진 예산을 여러 도로에 나누어 투자하여, 보수 후 1번 도시에서 가장 먼 도시까지 걸리는 시간이 가능한 한 작아지도록 하려고 한다.
그 최소 가능 시간을 구하여라.
입력
첫째 줄에 두 정수 N과 K (2 <= N <= 100000, 0 <= K <= 1000000)가 주어진다. N은 도시의 수이고, K는 사용할 수 있는 총 보수 예산(유로)이다.
다음 N - 1개의 줄에는 네 정수 X, Y, A, B (0 <= B <= A <= 10000)가 주어진다. 이는 도시 X와 도시 Y 사이에 도로가 있으며, A는 현재 이동 시간, B는 가능한 최소 이동 시간임을 뜻한다.
출력
보수 예산을 최적으로 배분했을 때, 1번 도시에서 가장 먼 도시까지 걸리는 최소 가능 시간을 나타내는 정수 하나를 출력한다.