Good Influencers

Υπάρχουν ~N\;(N \ge 2)~ μαθητές σε μια τάξη πληροφορικής, με διαφορετικές ταυτότητες μαθητών που αριθμούνται από το ~1~ έως το ~N~. Υπάρχουν ~N - 1~ φιλίες μεταξύ των μαθητών- η ~i~-οστή φιλία είναι μεταξύ των μαθητών ~A_{i}~ και ~B_{i}\;(A_{i} \neq B_{i},\;1 \le A_{i} \le N~ και ~1 \le B_{i} \le N)~. Κάθε ζεύγος μαθητών της τάξης είτε είναι φίλοι είτε συνδέονται κοινωνικά. Ένα ζευγάρι μαθητών ~a~ και ~b~ συνδέεται κοινωνικά, αν υπάρχει ένα σύνολο μαθητών ~m_{1}~, ~m_{2}~, ~. . .~ , ~m_{k}~ τέτοιο ώστε

• a και ~m_{1}~ είναι φίλοι,
• οι ~m_{i}~ και ~m_{i+1}~ είναι φίλοι (για ~1 \le i \le k - 1)~, και
• ~m_{k}~ και ~b~ είναι φίλοι.

Αρχικά, κάθε μαθητής ~i~ είτε σκοπεύει να συμμετάσχει στον CCC (αν το ~P_{i}~ είναι ~Y~) είτε δεν σκοπεύει να συμμετάσχει στον CCC (αν το ~P_{i}~ είναι ~N~). Αρχικά, τουλάχιστον ένας μαθητής σκοπεύει να συμμετάσχει στον CCC και τουλάχιστον ένας μαθητής δεν σκοπεύει να συμμετάσχει στον CCC.

Ο CCC έχει διαθέσει κάποια κονδύλια για να πληρώσει κάποιους φοιτητές για να είναι influencers για τον CCC. Ο CCC θα επιλέγει επανειλημμένα έναν φοιτητή ~i~ που σκοπεύει να λάβει μέρος στον CCC, θα τον πληρώσει ~C_{i}~ δολάρια και θα του ζητήσει να παραδώσει ένα σεμινάριο σε όλους τους φίλους του, και στη συνέχεια όλοι οι φίλοι του θα σκοπεύουν να λάβουν μέρος στον CCC.

Βοηθήστε τον CCC να προσδιορίσει το ελάχιστο κόστος που απαιτείται για να έχουν όλοι οι μαθητές πρόθεση να λάβουν μέρος στον CCC.

Είσοδος

Η πρώτη γραμμή θα περιέχει τον ακέραιο αριθμό ~N~.

Οι επόμενες ~N - 1~ γραμμές θα περιέχουν δύο ακέραιους αριθμούς η καθεμία, ~A_{i}~ και ~B_{i}\;(1 \le i \le N - 1)~.

Η επόμενη γραμμή θα περιέχει ~N~ χαρακτήρες, ~P_{1} . . . . P_{N}~ , καθένας από τους οποίους θα είναι είτε ~Y~ είτε ~N~.

Η επόμενη γραμμή θα περιέχει ~N~ ακέραιους αριθμούς χωρισμένους με κενά διαστήματα, ~C_{1} . . . . C_{N}~.

Για ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~2 \le N \le 2000~, ~1 \le C_{i} \le 1000~, ~A_{i} = i~, B_{i} = i + 1 για κάθε i.

Για επιπλέον ~7~ από τους ~15~ διαθέσιμους βαθμούς, ~2 \le N \le 2000~, ~1 \le C_{i} \le 1000~.

Για επιπλέον ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~2 \le N \le 200\;000~, ~1 \le C_{i} \le 1000~.

Έξοδος

Βγάλτε τον ελάχιστο ακέραιο αριθμό των δολαρίων που απαιτούνται για να έχουν όλοι οι μαθητές πρόθεση να λάβουν μέρος στον CCC.

Παραδείγματα

input

4
1 2
2 3
3 4
YNYN
4 3 6 2

output

6

Επεξήγηση του πρώτου παραδείγματος:

Ο CCC θα πρέπει να πληρώσει ~6~ δολάρια στον μαθητή ~3~ για να παραδώσει ένα σεμινάριο στους φίλους του (μαθητές ~2~ και ~4~), μετά από το οποίο και οι ~4~ μαθητές θα σκοπεύουν να λάβουν μέρος στον CCC.

input

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

output

6

Επεξήγηση του δεύτερου παραδείγματος:

Μια βέλτιστη στρατηγική για τον CCC είναι να ζητήσει από τους φοιτητές ~5~, ~1~, ~6~, ~11~, ~7~ και ~2~ να παραδώσουν σεμινάρια, με αυτή τη σειρά, πληρώνοντάς τους ~1~ δολάριο τον καθένα.