לתחנת הכוח 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$ מתקלקל.
• גנרטור יופעל אם המתג שלו דלוק והוא אינו מקולקל.

לבסוף תקבלו תגמולים מהגנרטורים הפעילים. תקבלו ין אחד עבור כל גנרטור פעיל. עם זאת, תצטרכו גם לשלם הוצאות תיקון על גנרטורים מקולקלים. תשלמו ין אחד עבור כל גנרטור מקולקל. סכום התגמולים הכולל פחות הוצאות התיקון הכוללות יהיה הרווח שלכם.

כתבו תוכנית שבהינתן סידור האתרים והכבלים והמידע על הגנרטורים, מחשבת את הרווח המרבי שלכם.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

$$ \begin{array}{ll} 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 ין ותשלמו ין אחד עבור תיקון. לכן הרווח שלכם יהיה 2 ין.

אם תעבירו את המתגים באתרים 1, 2, 5, 6 למצב דלוק, הגנרטור באתר 2 יתקלקל והגנרטורים באתרים 1, 5, 6 יופעלו. תקבלו 3 ין ותשלמו ין אחד עבור תיקון. לכן הרווח שלכם יהיה 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