Under construction

Still being built. Things may change

Road Repair

Time limit2sMemory limit128 MB

Summary
Given a tree with per-edge reducible travel times and a total repair budget, minimize the maximum distance from city 1 to any other city by optimally allocating budget across edges.
Level

Medium7 of 10

Topics
Binary search, Tree, Greedy, DFS
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

  1. Example 1

    Input
    3 200
1 2 200 100
2 3 450 250
    Expected output
    450

  2. Example 2

    Input
    5 11
1 2 10 5
1 3 3 2
1 4 9 6
3 5 7 3
    Expected output
    6

  3. Example 3

    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
    Expected output
    17