Архипелагта \(n\) арал орналасқан, олар \(n-1\) көпірмен байланысқан, және кез келген аралдан кез келген басқа аралға өтуге болады. \(i\) аралында \(a_i\) сиқырлы кристалдар бар.

Көпірлер периодты түрде тексеріледі. \(u\) және \(v\) аралдары арасындағы көпір уақытша бұзылады, және архипелаг екі бөлікке бөлінеді. Көпірді қалпына келтіру үшін, \(u\) аралын қамтитын жағындағы кристалдардың жалпы саны \(v\) аралын қамтитын жағындағы кристалдардың сомасынан қатаң көп болуы керек.

Тексерулер басталмас бұрын, кристалдарды ауыстыру операцияларын шексіз рет орындауға болады: бір операцияда \(x\) аралынан (мұнда \(a_x \ge 1\)) кез келген басқа \(y\) аралына бір кристалды ауыстыруға болады, \(a_x\)-ты 1-ге азайтып, \(a_y\)-ты 1-ге көбейту арқылы.

Барлық ауыстырулар алдын ала, тексерулер басталмай тұрып орындалуы керек. Тексерулер басталғаннан кейін кристалдарды ауыстыруға болмайды.

Барлық көпірлер тексеруден өтетіндей минималды ауыстырулар санын табыңыз, немесе бұл мүмкін емес болса, \(-1\) шығарыңыз.

Енгізу

Бірінші жолда бір бүтін сан \(n\) (\(2 \le n \le 2 \cdot 10^5\)) — аралдар саны.

Келесі \(n-1\) жолда, әрқайсысы екі бүтін сан \(u_i\) және \(v_i\) (\(1 \le u_i, v_i \le n\), \(u_i \neq v_i\)) — көпірлердің сипаттамасы.

Соңғы жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)) — әр аралдағы кристалдар саны.

Көпірлердің байланысқан ағашты құрайтынына кепілдік беріледі.

Шығару

Барлық тексерулерден өту үшін қажетті минималды кристалдарды ауыстырулар санын шығарыңыз, немесе \(-1\), егер бұл мүмкін болмаса.

Бағалау жүйесі

Мысалдар

Енгізу 1

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

Жауап 1

2

Ескертпелер

• \(1\)-ден \(3\)-ке бір кристалды ауыстыру.

• \(2\)-ден \(4\)-ке бір кристалды ауыстыру.