Để chuẩn bị cho giải đấu quốc tế, ban tổ chức quyết định thành lập một đội tuyển gồm các lập trình viên xuất sắc từ hai nền tảng LQDOJ và Codeforces. Có tất cả \(n\) ứng viên được xếp thành một hàng ngang từ vị trí \(1\) đến \(n\). Người thứ \(i\) có contribution là một số nguyên \(a_i\) (có thể âm hoặc dương). Ban tổ chức muốn chọn ra một đoạn liên tiếp các lập trình viên từ vị trí \(L\) đến \(R\) (\(1 \le L \le R \le n\)) để tham gia đội tuyển. Tuy nhiên, để đảm bảo sự hòa hợp giữa hai nền tảng, đoạn lập trình viên được chọn phải thỏa mãn điều kiện sau: Số lượng lập trình viên thuộc tổ chức LQDOJ trong đoạn \([L, R]\) phải không nhỏ hơn số lượng lập trình viên thuộc Codeforces.

Yêu cầu: Hãy in ra độ dài một đoạn \([L, R]\) thỏa mãn điều kiện trên sao cho tổng năng lực của các thành viên trong đoạn là lớn nhất có thể. Nếu không có đoạn nào thỏa mãn điều kiện, in ra 0.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)) — số lượng ứng viên.

• Dòng thứ hai chứa một chuỗi ký tự \(S\) có độ dài \(n\) chỉ gồm hai ký tự 'P' và 'C'. Ký tự thứ \(i\) bằng 'P' nếu người thứ \(i\) thuộc LQDOJ, và bằng 'C' nếu người đó thuộc Codeforces.

• Dòng thứ ba chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)) — contribution của từng người.

Output

• Một số nguyên duy nhất là tổng năng lực lớn nhất của đoạn chọn được. Nếu không chọn được đoạn nào, in ra 0.

Example

5
P C P C P
-2 5 4 -3 2

9