N개의 도시와 N-1개의 도로로 구성 되어있는 나라가 있다. 모든 도시는 서로 연결되어 있다.

오랫동안 관리를 안 한 탓에 도로들이 많이 훼손되어 있다. 각 도로당 두 개의 정수 A와 B가 주어진다 . A는 이 도로를 지날 때 걸리는 현재 시간, 그리고 B는 이 도로를 지날 때 걸리는 가능한 최소 시간이다.

우리는 얼마의 돈을 투자해서 도로 시스템을 조금 더 좋게 만들고자 한다. 어떤 도로를 개량하는데 E만큼의 돈을 투자하면 그 도로를 지날 때 걸리는 시간은 Max(A-E,B) 유닛 이다. E는 정수여야 된다.

당신은 도시 1에서부터 가장 오래 걸리는 도시까지 가는데 걸리는 시간을 최소화 하고 싶다. 가지고 있는 돈의 양이 주어지고 최선의 방법으로 도로를 개량한다고 했을 때 가능한 최소 시간을 구하시오.

입력

• 입력의 첫 번째 줄은 정수 N과 K (2<=N<=100 000, 0<=K<=1 000 000) 가 주어진다.K 는 주어진 돈이다.
• 다음 N-1줄에는 각각 네 개의 정수 X, Y, A, B 가 공백을 사이로 주어진다. (0<=B<=A<=10 000). X, Y는 도시 X 와 도시 Y를 연결하는 도로가 있다는 뜻이고 A와 B는 문제에서 말한 대로다.

출력

입출력 예

입력

3 200 
1 2 200 100 
2 3 450 250

출력 

450

입력 

5 11 
1 2 10 5 
1 3 3 2 
1 4 9 6 
3 5 7 3

출력 

6

출처:coci 2006
추천:likepad