Lumimyrsky on iskenyt laskettelukeskukseen ja rinteet kaipaavat pikaista aurausta.

Laskettelukeskus koostuu n rinteestä. Rinteet on yhdistetty toisiinsa yhteensä n-1 polulla siten, että rinne 1 on huipulla ja sieltä on alaspäin kulkeva reitti kaikille muille rinteille.

Lumiauralla voi kulkea rinteitä ja polkuja ainoastaan alaspäin ja aurata matkalle sattuvat rinteet. Jokaisesta rinteestä on tiedossa tarvittavien aurauskertojen määrä.

Lennätät helikopterilla lumiauroja vuoren huipulle. Mikä on pienin määrä lumiauroja, jolla kaikki rinteet saadaan aurattua?

Syöte

Ensimmäisellä rivillä on kokonaisluku n: rinteiden määrä.

Seuraa n-1 riviä lukuja a ja b: rinteeltä a on polku rinteelle b. Rinteet on numeroitu 1,2,\dots,n.

Viimeisellä rivillä on n lukua c_1, c_2, \dots, c_n: tarvittavien aurauskertojen määrä rinteille 1,2,\dots,n.

Tuloste

Tulosta yksi kokonaisluku: pienin tarvittava määrä lumiauroja.

Esimerkki

Syöte:

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

Tuloste:

6

Selitys: Laskettelukeskus on havainnollistettu kuvassa.

2 lumiauraa kulkee reitin (1,2), 3 lumiauraa reitin (1,3,4) ja 1 lumiaura reitin (1,3,5).

Osatehtävä 1 (53 pistettä)

• 1 \le n \le 100
• 0 \le c_i \le 100

Osatehtävä 2 (47 pistettä)

• 1 \le n \le 100\,000
• 0 \le c_i \le 10^9