Road Repair

A country's traffic network has N cities, numbered from 1 to N, and N - 1 roads connecting them. Between any two different cities, there is exactly one path.

The roads have been poorly maintained for years. For each road, two integers A and B are known. A is the current time in seconds needed to travel along the road, and B is the smallest possible travel time in seconds after fully repairing that road.

You have a fixed repair budget. Investing 1 euro in a road decreases its travel time by 1 second. The amount invested in each road must be an integer, and a road's travel time cannot be reduced below its minimum value B.

Distribute the given budget among the roads so that, after repairs, the travel time from city 1 to the farthest city is as small as possible.

Find that minimum possible time.

The first line contains two integers N and K (2 <= N <= 100000, 0 <= K <= 1000000): the number of cities and the total repair budget in euros.

Each of the next N - 1 lines contains four integers X, Y, A, and B (0 <= B <= A <= 10000). This means there is a road between cities X and Y; A is its current travel time and B is its minimum possible travel time.

Print one integer: the minimum possible time from city 1 to the farthest city after distributing the repair budget optimally.