== include(page="template/taskheader" task_id="oxificarelight") ==
In aceasta problema, trebuie sa amplasati $N + 1$ puncte pe axa numerelor reale, respectand anumite restrictii. Mai exact, vi se ofera un sir $lungime$, de $N$ elemente. Punctele trebuie amplasate pe axa astfel incat:
 
- Distanta pe axa dintre punctul cu numarul $i$ si punctul cu numarul $i + 1$ trebuie sa fie exact $lungime[i]$.
- Distanta dintre cel mai din stanga punct amplasat si cel mai din dreapta punct amplasat trebuie sa fie minim posibila.

Vi se da un arbore cu costuri pe muchii. Acest arbore trebuie sa fie "liniarizat" pe axa numerelor reale, in urmatorul sens:
- Fiecarui nod din arbore ii va fi asociat exact un punct de pe axa.
- Daca intre doua noduri $X$ si $Y$ exista *muchie* in arbore, atunci distanta dintre punctele asociate acestor noduri *trebuie* sa fie egala cu costul muchiei dintre ele.
- Distanta maxima dintre doua puncte asociate nodurilor trebuie sa fie minima.

h2. Date de intrare

Fişierul de intrare $oxificarelight.in$ va contine pe prima sa linie numarul de teste, $T$. Structura unui test este urmatoarea:

Fişierul de intrare $oxificare.in$ va contine pe prima sa linie valoarea intreaga $T$, reprezentand numarul de teste din fisier. Structura unui test este urmatoarea:
 
Prima linie va contine valoarea $N$, reprezentand numarul de noduri ale arborelui.

Pe prima linie se afla numarul natural $N$.

Cea de a doua linie va contine sirul $parinte$. Acesta este format din $N - 1$ valori, $parinte[i]$ reprezentand parintele nodului $i + 1$ in arbore. Nodul $1$ este radacina arborelui si nu are parinte. A se nota ca arborele este descris in acest fel doar cu scopul de a simplifica inputul, radacina fiind irelevanta in procesul de liniarizare a arborelui.

Pe a doua linie se afla $N$ numere naturale, reprezentand, in ordine, elementele sirului $lungime$.

Cea de a treia linie va contine la randul ei un sir $cost$ de $N - 1$ valori, unde $cost[i]$ reprezinta costul muchiei dintre nodul $i + 1$ si parintele sau.

h2. Date de ieşire

În fişierul de ieşire $oxificarelight.out$ se vor afla $T$ valori: pentru fiecare test trebuie sa afisati distanta minim posibila dintre punctul cel mai din stanga si punctul cel mai din dreapta intr-o amplasare optima.

În fişierul de ieşire $oxificare.out$ se va afla o singura valoare, reprezentand distanta maxima minim posibila in cazul unei liniarizari optime a arborelui.

h2. Restricţii

* $1 ≤ N ≤ 1.000$
* $1 ≤ lungime[i] ≤ 5.000$
* Suma valorilor lui $N$ in cadrul aceluiasi fisier de intrare este mai mica sau egala cu $6.000$.
* Pentru teste in valoare de $50$ de puncte, se garanteaza in plus ca $1 ≤ N, lungime[i] ≤ 100$, $1 ≤ T ≤ 25$.
* Printre acestea se afla teste in valoare de $20$ de puncte, pentru care se garanteaza in plus ca $lungime[i] ≤ lungime[i + 1]$ pentru toti $1 ≤ i ≤ N - 1$.

* $1 ≤ N ≤ 3.000$
* $1 ≤ cost[i] ≤ 10.000$
* $1 ≤ parinte[i] ≤ i$
* Pentru teste in valoare de $X$ puncte, se garanteaza in plus ca $parinte[i] = i$ pentru toti $1 ≤ i ≤ N - 1$. Cu alte cuvinte, arborele este un lant.

h2. Exemplu

table(example). |_. oxificarelight.in |_. oxificarelight.out |
| 2
3
5 5 5
3

table(example). |_. oxificare.in |_. oxificare.out |
| 1
4
1 2 3

5 4 5

| 5
6

| 6

|
h3. Explicaţie

O solutie pentru primul test este lista de puncte {1, 6, 1, 6}.
O solutie pentru cel de al doilea test este lista de puncte {0, 5, 1, 6}.
 
== include(page="template/taskfooter" task_id="oxificarelight") ==
 

...