Sinulle on annettuna puu, jossa on n solmua. Solmu 1 on puun juuri, ja jokaisella solmulla on tietty arvo.

Saat tehdä puuhun korkeintaan k poistoa. Jokaisessa poistossa saat valita minkä tahansa puun alipuun ja poistaa sen puusta.

Mikä on suurin mahdollinen solmujen arvojen summa poistojen jälkeen?

Syöte

Syötteen alussa on kaksi kokonaislukua n ja k: solmujen määrä ja poistojen määrä. Solmut on numeroitu 1,2,\ldots,n.

Sitten syötteessä on n kokonaislukua h_1,h_2,\ldots,h_n: jokaisen solmun arvo.

Lopuksi syötteessä on n-1 riviä, jotka kuvaavat puun rakenteen. Jokaisella rivillä on kaksi kokonaislukua a ja b: solmu b on solmun a lapsi.

Tuloste

Tulosta yksi kokonaisluku: suurin arvojen summa poistojen jälkeen.

Rajat

• 1 \le n \le 10^5
• 0 \le k \le \min(10,n)
• -10^9 \le h_i \le 10^9
• 1 \le a,b \le n

Esimerkki

Syöte:

5 2
2 -3 -9 5 3
1 2
1 3
3 4
3 5

Tuloste:

2