arbore

Cerință

Se dă un arbore (graf conex cu $N$ noduri și $N-1$ muchii) cu $N$ noduri cu costuri pe muchii. Se mai dau 2 siruri de lungime $N$, $st$ si $dr$.
Se cere sa alegeti niște muchii din cele $N-1$, astfel încât fiecare nod $i$ să aibă între $le_i$ si $ri_i$ muchii $\textbf{alese}$ adiacente cu el și suma costurilor muchiilor alese să fie minimă.
În cazul în care nu se pot alege niște muchii astfel încât să respecte condițiile pentru fiecare nod, se va afișa $-1$.

Date de intrare

Pe prima linie a fișierului de intrare arbore.in se găsește un număr $N$.
Pe a doua linie se găsesc $N$ numere, al $i$-lea dintre ele fiind $le_i$.
Pe a treia linie se găsesc $N$ numere, al $i$-lea dintre ele fiind $ri_i$.
Pe următoarele $N-1$ linii se găsesc trei numere $a_i$, $b_i$, $c_i$, reprezentând o muchie de costul $c_i$ între nodurile $a_i$ si $b_i$.

Date de ieșire

Pe prima linie a fișierului de ieșire arbore.out se va găsi un singur număr întreg, costul minim de a alege niște muchii sau -1 daca nu se pot alege.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $0 \leq le_i \leq ri_i \leq N$
• $0 \leq c_i \leq 10^9$
• $cnt_i$ este numărul de muchii legate cu nodul $i$

Exemplu

arbore.in

5
1 1 1 1 0
1 2 5 1 4
1 2 1
1 3 1
2 4 2
2 5 3

arbore.out

3

Explicație

O soluție corectă este de a alege prima și a treia muchie, care au costurile 1 respectiv 2, $1 + 2 = 3$.