In fiecare primãvarã drumurile sunt iar pline de gropi. Administratia localã analizeazã starea drumurilor pe o hartã pe care a marcat N localitãti (numerotate de la 1 la N) si N-1 drumuri. Un drum conecteazã douã localitãti, drumurile fiind selectate astfel încât între oricare douã localitãti sã existã legãturã.
Pentru fiecare drum de pe hartã sunt notate douã valori A si B: A reprezintã numãrul de secunde necesare pentru a parcurge drumul respectiv, iar B reprezintã numãrul de secunde necesare (minim posibil) pentru parcurgerea drumului în cazul în care drumul ar fi complet reparat.
Pentru repararea drumurilor existã un anumit buget. Pentru fiecare drum rezultatul va fi proportional cu suma de bani investitã în repararea drumului (suma de bani este întotdeauna un numãr întreg). Mai exact, pentru fiecare euro investit, timpul necesar pentru parcurgerea drumului se va reduce cu o secundã. Evident, timpul necesar parcurgerii drumului nu poate sã scadã sunt timpul minim necesar B.
Administratia localã intentioneze sã distribuie banii pentru repararea drumurilor astfel încât timpul necesar pentru a cãlãtori din localitatea 1 pânã la cea mai îndepãrtatã localitate sã fie cât mai mic posibil.

Cerinţă

Scrieti un program care sã determine timpul minim posibil necesar pentru a cãlãtori din localitatea 1 spre cea mai îndepãrtatã localitate, dupã repararea drumurilor folosind optim bugetul alocat.

Date de intrare

Fisierul de intrare gropi.in contine pe prima linie douã numere întregi N si K, numãrul de localitãti si respectiv suma bani pentru repararea drumurilor, exprimatã în euro. Fiecare dintre urmãtoarele N-1 linii contine câte 4 numere întregi X Y A B cu semnificatia "între localitãtile X si Y existã un drum care poate fi parcurs în A secunde; dacã ar fi reparat, drumul ar putea fi parcurs în minim B secunde". Valorile aflate pe aceeasi linie sunt separate prin spatii.

Date de ieşire

Fisierul de iesire gropi.out va contine o singura linie pe care va fi scris un singur numãr natural reprezentând timpul minim posibil necesar pentru a cãlãtori din localitatea 1 spre cea mai îndepãrtatã localitate, dupã repararea drumurilor folosind optim bugetul alocat.

Restricţii

• 2 <= N <= 100 000
• 0 <= K <= 1 000 000
• 0 <= B <= A <= 10 000
• 1 <= X, Y <= N

Exemple

gropi.in	gropi.out
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	17

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com