Cửa hàng vui vẻ đang bày bán ~ n ~ món đồ lưu niệm, được xếp thành một hàng và đánh số từ 1 đến ~ n ~ từ trái sang phải. Món đồ thứ ~ i ~ có khắc một ký tự ~ si ~ thuộc một trong sáu ký tự '{','}', '(', ')', '[', ']'. Độ đẹp của món đồ thứ ~ i ~ là ~ ci ~. Một người khách đến tham quan và muốn mua một dãy liên tiếp các món đồ, sao cho các ký tự trên các món đồ đó theo thứ tự lập thành một dãy ngoặc đúng. Hãy giúp vị khách chọn ra một dãy liên tiếp các món đồ thỏa mãn, sao cho tổng độ đẹp của các món đồ đó là lớn nhất có thể. Lưu ý, một dãy rỗng cũng được xem là một dãy thỏa mãn với tổng độ đẹp bằng 0.

Ở đây, dãy ngoặc đúng được định nghĩa như sau:

Xâu rỗng là một dãy ngoặc đúng;

Nếu A là một dãy ngoặc đúng thì (A), [A], {A} cũng là các dãy ngoặc đúng;

Nếu A và B là hai dãy ngoặc đúng thì AB là một dãy ngoặc đúng.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~ n ~ là số món đồ được bày bán;
• Dòng thứ hai chứa xâu ~ s ~ mô tả các ký tự trên các món đồ;
• Dòng thứ ba chứa ~ n ~ số nguyên ~ c_1, c_2, …, c_n ~ là độ đẹp của các món đồ.

Kết quả:

• Ghi một số nguyên duy nhất là tổng độ đẹp lớn nhất tìm được.

Ví dụ:

Input

10
}([{}]()))
5 -3 -2 5 -1 -1 2 4 2 6 

Output

7 

Giải thích: Vị khách sẽ mua các món đồ từ 3 đến 8.

Ràng buộc:

• Trong tất cả các test: ~ n ≤105; |c_i|≤10^9 ~.
• Có 16% số test với ~ n ≤100 ~ và xâu ~ s ~ chỉ chứa các ký tự '(' và ')'.
• Có 20% số test với ~ n ≤5000 ~.
• Có 24% số test với xâu ~ s ~ chỉ chứa các ký tự '(' và ')'.
• Có 40% số test với ràng buộc gốc.