Câu 4 (5.0 điểm) : Chuỗi tốt

Ta định nghĩa một chuỗi \(T\) có độ dài \(N\) chỉ gồm \(0\) và \(1\) được gọi là chuỗi tốt nếu chỉ tồn tại duy nhất một chỉ số \(i\) \((1 \le i \le N - 1)\) sao cho hai kí tự liên tiếp \(T_i\) và \(T_{i+1}\) giống nhau.

Bạn được cho một chuỗi \(S\) có độ dài \(N\) chỉ gồm các ký tự \(0\) và \(1\). Với mỗi vị trí \(i\) trong chuỗi, bạn có thể lựa chọn có thực hiện thao tác hay không; nếu thực hiện thì ký tự thứ \(i\) sẽ được đảo giá trị (\(0\) thành \(1\) hoặc \(1\) thành \(0\)) với chi phí tương ứng là \(C_i\).

Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất để biến chuỗi \(S\) thành một chuỗi tốt.

Input

Vào từ file CHUOITOT.INP gồm:

• Dòng đầu tiên chứa số nguyên dương \(n\) -- là độ dài xâu \(S\) \((2 \le n \le 2 \times 10^5)\).
• Dòng thứ hai chứa chuỗi \(S\) chỉ gồm các kí tự \(0\) hoặc \(1\).
• Dòng thứ ba chứa dãy \(c\) gồm \(n\) số nguyên dương \(c_1, c_2, \dots, c_n\) \((1 \le c_i \le 10^9)\) là chi phí phải bỏ ra nếu thực hiện thao tác đảo ký tự tại vị trí \(i\) trong chuỗi \(S\).

Output

Ghi ra file CHUOITOT.OUT một số nguyên duy nhất là tổng chi phí nhỏ nhất để biến chuỗi \(S\) thành một chuỗi tốt.

Example

5
00011
3 9 2 6 4

7

Scoring

• \(25\%\) số test: \(n \le 20\)
• \(25\%\) số test: \(n \le 100\)
• \(25\%\) số test: \(s\) là toàn kí tự giống nhau
• \(25\%\) số test: Không có ràng buộc gì thêm