Otkako se Krešo počeo baviti s uzgojem ljutih papričica, čak \(N\) restorana diljem Hrvatske zainteresiralo se za njegove papričice kako bi svoja jela obogatili pravim začinom. Zbog velikog interesa, Krešo je odlučio početi raditi kao dostavljač ljutih papričica.

Restorani su označeni brojevima od \(1\) do \(N\) i međusobno su povezani s \(N - 1\) cesta tako da je moguće putovanje između bilo koja dva restorana. Krešo svoje putovanje započinje kod restorana s oznakom \(1\). U jednoj jedinici vremena on se može odvesti do susjednog restorana ili dostaviti papričice u restoran kod kojeg se trenutno nalazi. Za svaki restoran poznata je tražena količina ljutih papričica \(A_i\).

Budući da dostavljanje umara čovjeka, Krešo je odlučio potrošiti ukupno \(M\) jedinica vremena na dostavu i putovanje, nakon čega planira uzeti odmor.

Odredite najveći broj papričica koje Krešo može dostaviti u zadanom vremenu. Možete pretpostaviti da Krešo sa sobom uvijek nosi neograničenu količinu papričica.

Ulazni​ podaci

U prvom retku nalaze se dva broja \(N\) i \(M\) \(( 1 \leq N, M \leq 500 )\), broj restorana i vrijeme koje Krešo planira provesti dostavljajući papričice.

U drugom retku nalazi se \(N\) prirodnih brojeva \(A_i\) \(( 1 \leq A_i \leq 10^6 )\), tražene količine ljutih papričica za sve restorane s oznakama od \(1\) do \(N\).

U sljedećih \(N - 1\) redaka nalaze se po dva broja \(U\) i \(V\) \((1 \leq U, V \leq N\), \(U \neq V)\) koji predstavljaju cestu između restorana \(U\) i \(V\).

Izlazni podaci

Ispišite najveću količinu papričica koju Krešo može dostaviti u zadanom vremenu.

Primjeri test​ podataka

Ulaz

3 5
9 2 5
1 2
1 3

Izlaz

14

Objašnjenje

U prvom koraku Krešo će dostaviti papričice u restoranu s oznakom \(1\).

U drugom koraku će putovati do restorana s oznakom \(3\).

U trećem koraku će dostaviti papričice u restoranu s oznakom \(3\).

Preostale su još \(2\) jedinice vremena, u kojima se može odvesti do restorana s oznakom \(2\), ali mu nedostaje jos \(1\) jedinica vremena da dostavi papričice u tom restoranu.

Ulaz

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

Izlaz

3

Ulaz

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

Izlaz

15