spiridusi

Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din $N$ camere, unite între ele prin $N-1$ culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera $1$. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră $i$ s-au stabilit $s_i$ spiriduși de praf.

Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere $a$ și $b$ (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera $b$ trece prin camera $a$. Fetele vor merge apoi din camera $a$ în camera $b$ pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele $a$ și $b$. După ce fetele ajung în camera $b$, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.

Fetele au stabilit pentru fiecare cameră $i$ un coeficient $p_i$ care reprezintă cât de plăcută ar fi camera $i$ pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de $C$ spiriduși ai prafului din camerele prin care trec.

Cerință

Cunoscând valorile lui $N$ și $C$, numărul de spiriduși ai prafului $s_i$, coeficienții $p_i$ pentru fiecare cameră $i$, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților $p$ ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

Date de intrare

Pe prima linie a fișierului de intrare spiridusi.in se vor afla două numere naturale $N$ și $C$ cu semnificația din enunț. Pe a doua linie se vor afla $N$ numere naturale separate prin câte un spațiu, al $i$-lea dintre acestea reprezentând numărul de spiriduși $s_i$ aflați în camera $i$. Pe a treia linie se vor afla $N$ numere întregi separate prin câte un spațiu, al $i$-lea dintre acestea reprezentând coeficientul $p_i$ al camerei $i$. Pe următoarele $N-1$ linii se vor afla câte două numere întregi $x$ și $y$ separate printr-un spațiu, semnificând existența unui culoar ce unește camerele $x$ și $y$.

Date de ieșire

În fișierul de ieșire spiridusi.out se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a coeficienților $p$ ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

Restricții și precizări

• $ 1 \leq N \leq 100 000$

• $ 1 \leq C \leq 20 000 000$

• $ 1 \leq s_i \leq 20 000 000$, pentru orice $i, 1 \leq i \leq N$

• $ -10 000 \leq p_i \leq 10 000$, pentru orice $i, 1 \leq i \leq N$

• $ 1 \leq x, y \leq N$

• Pentru 20% din teste, fiecare cameră are maximum $2$ vecini.

• Pentru 30% din teste, $ N \leq 1000$

• Se garantează că pentru orice cameră $x$, numărul total de spiriduși aflați în camerele de pe drumul cel mai scurt de la camera $1$ la camera $x$ nu depășește $1 000 000 000$.

Exemplu

spiridusi.in

6 8
2 4 6 2 4 1
3 10 11 -2 4 5
1 2
2 3
2 4
4 5
4 6

spiridusi.out

13

Explicaţii

Dacă alegem camerele $a = 2$ și $b = 6$, obținem un spațiu de joacă format din camerele $2$, $4$ și $6$.

Numărul total de spiriduși goniți din aceste camere este $4 + 2 + 1 = 7$, care este mai mic sau egal decât $C = 8$.

Suma coeficienților $p$ ai acestor camere este $10 + (-2) + 5 = 13$, maximul posibil ce se poate obține.