Elektrownia JOI ma $N$ baz ponumerowanych od $1$ do $N$. Bazy są połączone $N-1$ przewodami. $i$-ty przewód ($1 \le i \le N-1$) łączy bazę $A_i$ z bazą $B_i$ w obu kierunkach. Z każdej bazy można dotrzeć do każdej innej, przechodząc wzdłuż przewodów.

W każdej bazie elektrowni JOI znajduje się co najwyżej jeden generator prądu. Każdy generator ma przełącznik. Początkowo wszystkie przełączniki są wyłączone (OFF). Jesteś dyrektorem elektrowni JOI. Możesz wybrać pewne generatory i ustawić ich przełączniki w pozycji włączonej (ON). (Można nie wybrać żadnego generatora.) Generatory mają następujące właściwości.

• Załóżmy, że w bazach $x$, $y$, $z$ znajdują się generatory. Załóżmy ponadto, że można przejść z bazy $x$ do bazy $y$, a następnie z bazy $y$ do bazy $z$, nie przechodząc dwukrotnie wzdłuż tego samego przewodu. Jeśli przełączniki generatorów w bazach $x$ i $z$ są włączone, generator w bazie $y$ ulega uszkodzeniu.
• Generator działa, jeśli jego przełącznik jest włączony i generator nie jest uszkodzony.

Na koniec otrzymasz wynagrodzenie za działające generatory: po 1 jenie za każdy z nich. Musisz jednak również zapłacić za naprawę uszkodzonych generatorów: po 1 jenie za każdy uszkodzony generator. Twój zysk to łączne wynagrodzenie pomniejszone o łączne koszty napraw.

Napisz program, który na podstawie rozmieszczenia baz i przewodów oraz informacji o generatorach obliczy maksymalny zysk.

Wejście

Wczytaj ze standardowego wejścia następujące dane.

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

$S$ jest napisem długości $N$ opisującym generatory w bazach. Każdy znak $S$ to 0 lub 1. $i$-ty znak ($1 \le i \le N$) opisuje generator w bazie $i$. Ma wartość 0, jeśli w bazie $i$ nie ma generatora, lub 1, jeśli generator się tam znajduje.

Wyjście

Wypisz jeden wiersz na standardowe wyjście. Powinien on zawierać maksymalny zysk, jaki możesz uzyskać, wybierając pewne generatory i włączając przełączniki wszystkich wybranych generatorów.

Ograniczenia

• $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$).
• Z każdej bazy można dotrzeć do każdej innej, przechodząc wzdłuż przewodów.
• $S$ jest napisem długości $N$ złożonym ze znaków 0, 1.
• $S$ zawiera co najmniej jedną 1.

Podzadania

1. (6 punktów) $N \le 16$.
2. (41 punktów) $N \le 2\,000$.
3. (53 punkty) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

3

Uwagi

W tym przykładzie generatory znajdują się w bazach $1$, $2$, $5$, $6$.

Jeśli włączysz przełączniki w bazach $1$, $2$, $5$, generatory w tych bazach będą działać i otrzymasz 3 jeny. Ponieważ nie poniesiesz kosztów napraw, twój zysk wyniesie 3 jeny. Jest to maksymalny zysk, więc należy wypisać $3$.

Jeśli natomiast włączysz przełączniki w bazach $1$, $5$, $6$, generator w bazie $2$ ulegnie uszkodzeniu, a generatory w bazach $1$, $5$, $6$ będą działać. Otrzymasz 3 jeny i zapłacisz 1 jena za naprawę. Twój zysk wyniesie więc 2 jeny.

Jeśli włączysz przełączniki w bazach $1$, $2$, $5$, $6$, generator w bazie $2$ ulegnie uszkodzeniu, a generatory w bazach $1$, $5$, $6$ będą działać. Otrzymasz 3 jeny i zapłacisz 1 jena za naprawę. Twój zysk wyniesie więc 2 jeny.

Wejście 2

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

Wyjście 2

3

Wejście 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

Wyjście 3

5