A fost odată ca-n povești,
A fost ca niciodată,
Din rude mari împărătești,
Un prea frumos arbore cu $n$ noduri.

Cerință

Gigel, un mare informatician (supranumit luceafărul informaticii românești), vrea să coloreze preafrumosul arbore folosind $m$ culori, codificate prin numerele naturale de la $1$ la $m$.

După ce a asociat fiecărei culori $c$ o pondere $w_c$ și fiecărui nod $u$ o valoare $req_u$, Gigel a zis că o colorare a nodurilor arborelui este bună dacă fiecare nod $u$ respectă una dintre următoarele condiții:

1. Nodul $u$ are culoarea $1$; sau
2. Dacă nodul $u$ are culoarea $c>1$, atunci el are exact $req_u$ vecini cu culoarea $c-1$.

Tot Gigel definește valoarea unei astfel de colorări ca fiind $w_{c_1}+w_{c_2}+\ldots+w_{c_n}$, unde $c_u$ reprezintă culoarea nodului $u$.

Ajutați-l pe Gigel să afle cea mai mare valoare a unei colorări bune!

Date de intrare

Pe prima linie din fişierul de intrare warb.in se vor găsi două numere naturale $n$ și $m$ — numărul de noduri din arbore, respectiv numărul de culori.
Pe a doua linie se vor găsi $m$ numere naturale $w_1,w_2,\ldots,w_m$ — ponderile celor $m$ culori.
Pe a treia linie se vor găsi $n$ numere naturale $req_1,req_2,\ldots,req_n$ — valorile asociate celor $n$ noduri.
Pe următoarele $n-1$ linii se vor găsi câte 2 numere naturale $u$ si $v$, semnificând faptul că există o muchie în arbore între nodurile $u$ și $v$.

Date de iesire

Pe prima linie din fişierul de ieşire warb.out se va afişa un singur număr natural, cea mai mare $valoare$ a unei colorari $bune$.

Restricții și precizări

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 100$
• $1 \leq w_i \leq 10^4$
• $0 \leq req_i \leq$ gradul nodului $i$.
• Se garantează că graful din fișierul de intrare este un arbore (un graf neorientat conex aciclic).
• Pentru a obține punctele pentru un anumit subtask, cel puțin o sursă trimisă va trebui să treacă toate testele din acel subtask.

  #	Punctaj	Restricții
  0	0	Exemple
  1	4	$n=1$
  2	4	$m=1$
  3	22	$n,m \le 7$
  4	10	$req_i=0$
  5	8	$m \le 10$, arborele este un lanț (gradele tuturor nodurilor sunt mai mici sau egale cu $2$)
  6	7	arborele este un lanț
  7	10	arborele este o stea (există un nod cu gradul $n-1$)
  8	19	$m, \text{gradele tuturor nodurilor} \leq 10$
  9	6	$req_i > 0$
  10	10	Fără restricții suplimentare

Exemplul 1

warb.in

3 2
1 2
1 1 1
1 2
1 3

warb.out

5

Explicație

Pentru primul exemplu, o colorare optimă este $c=[1,2,2]$:

• Nodul $1$ are culoarea $1$.
• Nodul $2$ are culoarea $2$ și exact un vecin cu culoarea $c_2-1=1$.
• Nodul $3$ are culoarea $2$ și exact un vecin cu culoarea $c_3-1=1$.
• Valoarea acestei colorări este egală cu $w_{c_1}+w_{c_2}+w_{c_3}=w_1+w_2+w_2=1+2+2=5$.

Exemplul 2

warb.in

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

warb.out

8

Explicație

Pentru al doilea exemplu, o colorare optimă este $c=[2,1,1,2,2]$:

• Nodul $1$ are culoarea $2$ și exact doi vecini cu culoarea $c_1-1=1$.
• Nodul $2$ are culoarea $1$.
• Nodul $3$ are culoarea $1$.
• Nodul $4$ are culoarea $2$ și exact un vecin cu culoarea $c_4-1=1$.
• Nodul $5$ are culoarea $2$ și exact un vecin cu culoarea $c_5-1=1$.
• Valoarea acestei colorări este egală cu $w_{c_1}+w_{c_2}+w_{c_3}+w_{c_4}+w_{c_5}=2+1+1+2+2=8$.

Exemplul 3

warb.in

7 4
1 9 8 7
2 2 0 0 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7

warb.out

46

Explicație

Pentru al treilea exemplu, o colorare optimă este $c=[2,1,1,3,2,2,2]$.

Exemplul 4

warb.in

6 5
7 9 50 30 80
0 1 0 0 1 0
1 2
2 3
3 4
3 5
5 6

warb.out

380

Explicație

Pentru al patrulea exemplu, o colorare optimă este $c=[4,5,5,5,5,4]$.

Exemplul 5

warb.in

7 7
458 2960 8526 2565 6679 9621 8814
1 0 0 0 2 1 1
3 4
1 2
1 4
5 7
4 5
4 6

warb.out

49102

Explicație

Pentru al cincilea exemplu, o colorare optimă este $c=[7,7,6,6,1,7,2]$.

Exemplul 6

warb.in

7 7
3564 9408 8285 6312 7323 3223 4441
0 0 0 1 1 1 2
3 2
5 3
4 1
7 3
4 7
6 7

warb.out

54831

Explicație

Pentru al șaselea exemplu, o colorare optimă este $c=[2,2,4,2,5,2,1]$.