Vi se dă un arbore cu costuri pe muchii. Acest arbore trebuie să fie "liniarizat" pe axa numerelor reale, în următorul sens:

* Fiecărui nod din arbore îi va fi asociat exact un punct de pe axă. Cele $N$ puncte nu trebuie sa fie neaparat distincte.

* Fiecărui nod din arbore îi va fi asociat exact un punct de pe axă. Cele $N$ puncte *nu trebuie* sa fie neaparat distincte.

* Dacă între două noduri $X$ şi $Y$ există *muchie* în arbore, atunci distanţa dintre punctele asociate acestor noduri *trebuie* să fie egală cu costul muchiei dintre ele.
* Distanţa maximă dintre două puncte asociate nodurilor trebuie să fie minimă.

* Suma valorilor lui $N$ in cadrul aceluiasi fisier de intrare nu depaseste valoarea $3.000$.
* Toate valorile din input sunt numere naturale.
* Pentru teste in valoare de $50$ de puncte, se garantează în plus că $parinte[i] = i$ pentru toţi $1 ≤ i ≤ N - 1$. Cu alte cuvinte, arborele este un lanţ.

* Dintre acestea, pentru teste in valoare de $20$ de puncte, se garanteaza in plus ca $1 ≤ N, lungime[i] ≤ 100$, respectiv $1 ≤ T ≤ 25$.

* Dintre acestea, pentru teste in valoare de $20$ de puncte, se garanteaza in plus ca $1 ≤ N, cost[i] ≤ 100$, respectiv $1 ≤ T ≤ 25$.

h2. Exemplu