Электростанция 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}{l} 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, если генератор есть.

Выходные данные

Выведите одну строку в стандартный вывод. Она должна содержать максимально возможную прибыль при выборе некоторых генераторов и включении всех переключателей выбранных генераторов.

Ограничения

• $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