Електростанція JOI має $N$ вузлів, пронумерованих від $1$ до $N$. Вузли з'єднані $N-1$ проводами. $i$-й провід ($1 \le i \le N-1$) з'єднує вузол $A_i$ з вузлом $B_i$ в обох напрямках. Можна дістатися з будь-якого вузла до будь-якого іншого, пройшовши деякими проводами.

У кожному вузлі електростанції JOI є щонайбільше один електрогенератор. Кожен генератор має перемикач. Спочатку перемикачі всіх генераторів вимкнені. Ви — директор електростанції JOI. Ви можете вибрати деякі генератори та ввімкнути їхні перемикачі. (Дозволяється не вибирати жодного.) Генератори мають такі властивості.

• Припустімо, що у вузлах $x,y,z$ є генератори. Також припустімо, що можна пройти з вузла $x$ до вузла $y$, а потім із вузла $y$ до вузла $z$, не проходячи тим самим проводом двічі. Якщо перемикачі генераторів у вузлах $x$ та $z$ увімкнені, генератор у вузлі $y$ ламається.
• Генератор працюватиме, якщо його перемикач увімкнений і він не зламаний.

Зрештою ви отримаєте винагороду за генератори, що працюють. За кожен такий генератор ви отримаєте 1 єну. Проте вам також доведеться сплатити витрати на ремонт зламаних генераторів: по 1 єні за кожен зламаний генератор. Загальна сума винагород за вирахуванням загальних витрат на ремонт становитиме ваш прибуток.

Напишіть програму, яка за розташуванням вузлів і проводів та інформацією про генератори обчислить найбільший можливий прибуток.

Вхідні дані

Прочитайте такі дані зі стандартного вводу.

$$ \begin{array}{cc} N \\ A_1 & B_1 \\ \vdots \\ A_{N-1} & B_{N-1} \\ S \end{array} $$

Тут $S$ — рядок довжини $N$, що описує генератори у вузлах. Кожен символ $S$ — це 0 або 1. $i$-й символ ($1 \le i \le N$) описує генератор у вузлі $i$: 0 означає, що у вузлі $i$ немає генератора, а 1 — що у вузлі $i$ є генератор.

Вихідні дані

Виведіть один рядок у стандартний вивід. Він має містити найбільший можливий прибуток, якщо вибрати деякі генератори та ввімкнути перемикачі всіх вибраних генераторів.

Обмеження

• $1 \le N \le 200\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N-1$).
• $1 \le B_i \le N$ ($1 \le i \le N-1$).
• $A_i \ne B_i$ ($1 \le i \le N-1$).
• Можна дістатися з будь-якого вузла до будь-якого іншого, пройшовши деякими проводами.
• $S$ — рядок довжини $N$, що складається із символів 0 та 1.
• $S$ містить принаймні один символ 1.

Підзадачі

1. (6 балів) $N \le 16$.
2. (41 бал) $N \le 2\,000$.
3. (53 бали) Без додаткових обмежень.

Приклади

Вхідні дані 1

6
2 3
4 3
1 3
3 5
6 2
110011

Вихідні дані 1

3

Пояснення

У цьому прикладі генератори є у вузлах $1,2,5,6$.

Якщо ввімкнути перемикачі у вузлах $1,2,5$, генератори у вузлах $1,2,5$ працюватимуть, і ви отримаєте 3 єни. Оскільки витрат на ремонт не буде, ваш прибуток становитиме 3 єни. Це найбільший можливий прибуток, тому виведіть 3.

Натомість, якщо ввімкнути перемикачі у вузлах $1,5,6$, генератор у вузлі $2$ зламається, а генератори у вузлах $1,5,6$ працюватимуть. Ви отримаєте 3 єни та сплатите 1 єну за ремонт. Отже, ваш прибуток становитиме 2 єни.

Якщо ввімкнути перемикачі у вузлах $1,2,5,6$, генератор у вузлі $2$ зламається, а генератори у вузлах $1,5,6$ працюватимуть. Ви отримаєте 3 єни та сплатите 1 єну за ремонт. Отже, ваш прибуток становитиме 2 єни.

Вхідні дані 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

Вихідні дані 2

3

Вхідні дані 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

Вихідні дані 3

5