Có $N$ viên đá được đánh số từ $1$ đến $N$ được xếp thành một hàng theo thứ tự tăng dần. Mỗi viên đá có màu trắng hoặc đen. Khối lượng của viên đá thứ $i$ là $A_i$.

Bạn sẽ lần lượt loại bỏ từng viên đá một cho đến khi tất cả các viên đá đều được loại bỏ.

Khi loại bỏ một viên đá, nếu viên đá đó không phải là viên đá ngoài cùng bên trái hoặc ngoài cùng bên phải trong số các viên đá còn lại, và cả hai viên đá kề cạnh với viên đá đang được loại bỏ đều có màu khác với nó, điểm số của bạn sẽ tăng thêm một lượng bằng khối lượng của viên đá được loại bỏ. Hai viên đá được gọi là kề cạnh nếu không có viên đá nào khác nằm giữa chúng.

Hãy tìm cách loại bỏ các viên đá để tối đa hóa điểm số của bạn.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương $N$ ($1 \le N \le 3 \times 10^5$).

Dòng thứ hai chứa một chuỗi $S$ có độ dài $N$ chỉ gồm các ký tự B hoặc W. Ký tự thứ $i$ của $S$, ký tự $S_i$, là B nếu viên đá thứ $i$ có màu đen, và là W nếu viên đá thứ $i$ có màu trắng.

Dòng thứ ba chứa $N$ số nguyên $A_1, A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$). $A_i$ đại diện cho khối lượng của viên đá thứ $i$.

Dữ liệu ra

In ra điểm số tối đa có thể đạt được nếu bạn loại bỏ các viên đá một cách tối ưu.

Ví dụ

Dữ liệu vào 1

4
WBWB
6 4 5 3

Dữ liệu ra 1

5

Dữ liệu vào 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

Dữ liệu ra 2

13

Ghi chú

Nếu ta lần lượt loại bỏ các viên đá ở vị trí thứ 5, 6, 2, 3, 4, 7, 8, 1 (tính từ trái sang phải theo vị trí ban đầu), ta sẽ nhận được điểm khi loại bỏ viên đá thứ 3 và thứ 5, tổng điểm đạt được là 13.