MROADS  Roads Repair
English  Vietnamese 
The traffic network in a country consists of N cities (labeled with integers 1 to N) and N1 roads connecting the cities. There is a unique path between each pair of different cities.
Because of the many years of lazy maintenance the roads are pretty damaged and for each road two numbers A and B are known – the integer A represents the current time (in seconds) needed to travel along the road, and the integer B represents the smallest possible time (in seconds) needed to travel along this road if we repair all the damage.
We want to invest a certain amount of money into road repair. For a particular road, the result will be proportional to the amount of invested money. For each euro invested in some road, the time needed to travel along that road will be reduced by one second (the amount of money invested in some road has to be an integer). The travel time cannot be reduced beyond the smallest possible time B described above.
We are given a certain amount of money. We want to distribute this money along different roads in such a way that the time needed to travel from the city 1 to the most distant city (after all the repairs) is as small as possible.
Write a program that will find this smallest time.
Input
The first line of input contains two integers N and K, 2 ≤ N ≤ 100 000, 0 ≤ K ≤ 1 000 000, the number of cities and the total amount of money (in euros).
Each of the next N1 lines contains four integers X, Y, A and B, 0 ≤ B ≤ A ≤ 10 000. It means that there is a road between cities X and Y, with the numbers A and B representing the current time and the minimum time as described above.
Output
The first and only line of output should contain a single integer – the minimum time from the task description.
Sample
input
3 200
1 2 200 100
2 3 450 250
output
450
input
5 11
1 2 10 5
1 3 3 2
1 4 9 6
3 5 7 3
output
6
input
11 12
1 2 7 5
1 3 20 15
2 4 10 8
2 5 5 3
2 6 6 2
4 7 3 0
4 8 7 2
5 9 8 4
5 10 9 8
5 11 6 5
output
17
hide comments
mhamed_resli:
20180130 18:43:56
AC after 6 TLE . nice problem! 

Tomek Jurkiewicz:
20170120 13:05:44
@Jelle van den Hooff: solution is O(n lg(k)) 

coding_express:
20130528 11:06:05
please explain test case no 3


Sigma Kappa:
20110529 12:47:53
@kush sharma: the answer is indeed "17". Last edit: 20110529 15:04:32 

Kush Sharma:
20110319 17:19:51
can u explain the third test case..?


amaroq:
20090608 08:20:33
'Most distant city' refers to the city to which it takes the most time to get to, rather than deepest in the tree. I found this a bit confusing at first. 

Jelle van den Hooff:
20090607 19:24:40
Time limit seems to be rather strict for my O(K lg(n)) (I even think it's more like n lg(n)) Last edit: 20090607 18:31:04 
Added by:  ~!(*(@*!@^& 
Date:  20090606 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 06 