Những con mèo của Nam lần này được chơi trò phá bóng bay. Nam có ~n~ bóng bay xếp từ trái sang phải với màu của nó được biểu diễn bằng 1 xâu chỉ gồm 3 chữ cái ~a~,~b~,~c~ viết thường tương ứng với ~3~ màu khác nhau, Nam đã có thể tính toán chính xác thời gian cần để các con mèo phá nổ quả bóng thứ ~i~ là ~a_i~ giây. Các con mèo chỉ có thể phá từng quả bóng một và các con mèo sẽ phá bóng cho đến khi không còn 2 quả bóng nào đứng cạnh nhau có màu giống nhau.

Nam nhờ bạn tính thời gian ít nhất có thể để các con mèo phá các quả bóng sao cho không quả bóng nào đứng cạnh nhau có màu giống nhau.

Input

Dòng đầu gồm 1 số nguyên ~n~ ~(1≤n≤10^6)~ số lượng quả bóng bay.

Dòng tiếp theo gồm 1 xâu có độ dài ~n~ là màu các quả bóng, xâu chỉ gồm kí tự ~‘a’~, ~‘b’~ và ~‘c’~.

Dòng tiếp theo gồm n số nguyên dương ~a_i~ ~(0<a_i≤10^9)~ thời gian để nhưng con mèo làm nổ quả bóng thứ ~i~.

Output

1 số nguyên duy nhất là thời gian ít nhất để các con mèo phá các quả bóng sao cho không quả bóng nào đứng cạnh nhau có màu giống nhau.

Sample Input

5
abaac
1 2 3 4 5

Sample Output

3