Alice, Bob và hai đội

Alice và Bob chia $n$ quân cờ thành hai đội. Quân thứ $i$ có sức mạnh $p_i$.

Quá trình chia gồm các bước:

1. Alice chia $n$ quân cờ thành hai nhóm bằng cách viết một xâu $s$ độ dài $n$ gồm các ký tự A hoặc B — nếu $s_i=$ A thì quân $i$ thuộc về Alice, ngược lại thuộc về Bob.
2. Bob được chọn một tiền tố hoặc một hậu tố bất kỳ của xâu $s$ (có thể rỗng) và đảo toàn bộ các ký tự trong đoạn đó (A thành B và B thành A). Bob được làm thao tác này nhiều nhất một lần (có thể không làm).
3. Sau khi Bob xử lý xong, Alice nhận tất cả quân được đánh dấu A, Bob nhận tất cả quân được đánh dấu B.

Sức mạnh của một người chơi bằng tổng sức mạnh các quân cờ thuộc về người đó. Cho xâu $s$ ban đầu Alice viết ra, hãy giúp Bob tìm chiến lược tối ưu và in ra sức mạnh lớn nhất mà Bob có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số lượng quân cờ.
• Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$ — sức mạnh của các quân cờ.
• Dòng thứ ba chứa xâu $s$ độ dài $n$ gồm các ký tự A và B — cách chia đội ban đầu của Alice.

Dữ liệu ra

In ra một số nguyên duy nhất — sức mạnh lớn nhất Bob có thể đạt được.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $1\le p_i\le {10}^9$
• $s$ chỉ chứa các ký tự A và B.

Ví dụ