시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)147541937029.984%

문제

$N$ 개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다. 

돌들을 왼쪽부터 1번 돌, 2번 돌,$\cdots$, $N$번 돌이라 하자. $i$번째 돌의 무게는 $A_i$이다.

당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 총 $N$번 반복하려고 한다.

돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.

가장 많은 점수를 얻을 수 있도록 돌을 가져가는 방법을 구하여라.

입력

첫 줄에 양의 정수 $N$이 주어진다. ($1 \le N \le 3 \times 10^5$)

둘째 줄에 B 또는 W로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

$S$의 $i$번째 문자 $S_i$는 왼쪽에서 $i$번째 돌의 색을 나타낸다. B는 돌이 검은색임을, W는 돌이 흰색임을 뜻한다.

셋째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어진다. ($1 \le A_i \le 10^9$)

$A_i$ 는 $i$번 돌의 무게를 나타낸다. 

출력

첫째 줄에 최적의 방법으로 돌을 가져갔을 때 얻을 수 있는 점수를 출력한다.

예제 입력 1

8
WBBWBWBB
6 4 8 2 5 3 1 5

예제 출력 1

13

노트

처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다.

W3sicHJvYmxlbV9pZCI6IjIyMzU0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2NjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+JE4kIFx1YWMxY1x1Yzc1OCBcdWIzY2NcdWM3NzQgXHVjNzdjXHViODJjXHViODVjIFx1YjA5OFx1YzVmNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWIzY2NcdWM3NDAgXHVkNzcwXHVjMGM5IFx1YjYxMFx1YjI5NCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViM2NjXHViNGU0XHVjNzQ0IFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCAxXHViYzg4IFx1YjNjYywgMlx1YmM4OCBcdWIzY2MsJFxcY2RvdHMkLCAkTiRcdWJjODggXHViM2NjXHVjNzc0XHViNzdjIFx1ZDU1OFx1Yzc5MC4gJGkkXHViYzg4XHVjOWY4IFx1YjNjY1x1Yzc1OCBcdWJiMzRcdWFjOGNcdWIyOTQgJEFfaSRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBcdWIwOThcdWM1ZjRcdWI0MWMgXHViM2NjXHViNGU0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NDQgXHViYWE4XHViNGUwIFx1YjNjY1x1Yzc3NCBcdWM1YzZcdWM1YjRcdWM5YzggXHViNTRjXHVhZTRjXHVjOWMwIFx1Y2QxZCAkTiRcdWJjODggXHViYzE4XHViY2Y1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2NjXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwOCBcdWI1NGMsIFx1YjljY1x1YzU3ZCBcdWFkZjggXHViM2NjXHVjNzc0IFx1ZDYwNFx1YzdhYyBcdWIwOThcdWM1ZjRcdWI0MWMgXHViM2NjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzQgXHVjNTQ0XHViMmM4XHViYTcwLCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2NjXHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViM2NjIFx1YmFhOFx1YjQ1MCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2NjXHVhY2ZjIFx1YjJlNFx1Yjk3OCBcdWMwYzlcdWM3NzggXHVhY2JkXHVjNmIwIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2NjXHVjNzU4IFx1YmIzNFx1YWM4Y1x1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWIzY2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzAwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxIFxcbGUgTiBcXGxlIDMgXFx0aW1lcyAxMF41JCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCA8Y29kZT5CPFwvY29kZT4gXHViNjEwXHViMjk0IDxjb2RlPlc8XC9jb2RlPlx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0ICROJFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFMkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JFMkXHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTAgJFNfaSRcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjICRpJFx1YmM4OFx1YzlmOCBcdWIzY2NcdWM3NTggXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gPGNvZGU+QjxcL2NvZGU+XHViMjk0IFx1YjNjY1x1Yzc3NCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3ODRcdWM3NDQsIDxjb2RlPlc8XC9jb2RlPlx1YjI5NCBcdWIzY2NcdWM3NzQgXHVkNzcwXHVjMGM5XHVjNzg0XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMSBcXGxlIEFfaSBcXGxlIDEwXjkkKTxcL3A+XHJcblxyXG48cD4kQV9pJCBcdWIyOTQgJGkkXHViYzg4IFx1YjNjY1x1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzE0XHVjNzQ0IFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjOThcdWM3NGMgXHVjNzA0XHVjZTU4IFx1YWUzMFx1YzkwMCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgJDUsXFwgNixcXCAyLFxcIDMsXFwgNCxcXCA3LFxcIDgsXFwgMSRcdWJjODhcdWM5ZjggXHViM2NjXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQgJDMkXHViYzg4XHVjOWY4IFx1YjNjY1x1YWNmYyAkNSRcdWJjODhcdWM5ZjggXHViM2NjXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwOCBcdWI1NGMgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YzViNCAkMTMkXHVjODEwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIyMzU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RvbmVzIDEiLCJkZXNjcmlwdGlvbiI6IjxwPiROJCZuYnNwO3N0b25lcyBsYWJlbGVkIGZyb20mbmJzcDskMSQmbmJzcDt0byZuYnNwOyROJCZuYnNwO2FyZSBhcnJhbmdlZCBpbiBhIHJvdyBpbiBpbmNyZWFzaW5nIG9yZGVyLiBFYWNoIHN0b25lIGlzIGNvbG9yZWQgZWl0aGVyIHdoaXRlIG9yIGJsYWNrLiBUaGUgd2VpZ2h0IG9mIHRoZSZuYnNwOyRpJC10aCBzdG9uZSBpcyZuYnNwOyRBX2kkLjxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCByZW1vdmUgdGhlIHN0b25lcyBvbmUgYXQgYSB0aW1lIHVudGlsIGFsbCB0aGUgc3RvbmVzIGFyZSByZW1vdmVkLjxcL3A+XHJcblxyXG48cD5XaGVuIHJlbW92aW5nIGEgc3RvbmUsIGlmIHRoZSBzdG9uZSBpcyBub3QgdGhlIGxlZnRtb3N0IG9yIHJpZ2h0bW9zdCBvZiBhbGwgcmVtYWluaW5nIHN0b25lcywgYW5kIG5laXRoZXIgc3RvbmUgYWRqYWNlbnQgdG8gdGhlIHN0b25lIGJlaW5nIHJlbW92ZWQgbWF0Y2hlcyBpdCBpbiBjb2xvciwgeW91ciBzY29yZSBpbmNyZWFzZXMgYnkgdGhlIHdlaWdodCBvZiB0aGUgc3RvbmUgYmVpbmcgcmVtb3ZlZC4gVHdvIHN0b25lcyBhcmUgYWRqYWNlbnQgaWYgdGhlcmUgYXJlIG5vIHN0b25lcyBpbiBiZXR3ZWVuIHRob3NlIHR3by48XC9wPlxyXG5cclxuPHA+RmluZCBhIHdheSB0byByZW1vdmUgdGhlIHN0b25lcyB0byBtYXhpbWl6ZSB5b3VyIHNjb3JlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciZuYnNwOyROJCZuYnNwOygkMSBcXGxlIE4gXFxsZSAzMDBcXCwgMDAwJCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHN0cmluZyZuYnNwOyRTJCZuYnNwO29mIGxlbmd0aCZuYnNwOyROJCZuYnNwO3doZXJlIGVhY2ggY2hhcmFjdGVyIGlzIGVpdGhlciZuYnNwOzxjb2RlPkI8XC9jb2RlPiZuYnNwO29yJm5ic3A7PGNvZGU+VzxcL2NvZGU+LiBUaGUmbmJzcDskaSR0aCBjaGFyYWN0ZXIgb2YmbmJzcDskUyQsJm5ic3A7JFNfaSQsIGlzJm5ic3A7PGNvZGU+QjxcL2NvZGU+Jm5ic3A7aWYgdGhlJm5ic3A7JGkkLXRoIHN0b25lIGlzIGJsYWNrLCBvdGhlcndpc2UsJm5ic3A7JFNfaSQmbmJzcDtpcyZuYnNwOzxjb2RlPlc8XC9jb2RlPiZuYnNwO2FuZCB0aGUmbmJzcDskaSQtdGggc3RvbmUgaXMgd2hpdGUuPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zJm5ic3A7JE4kJm5ic3A7aW50ZWdlcnMmbmJzcDskQV8xLCBBXzIsIFxcY2RvdHMsIEFfTiQmbmJzcDsoJDEgXFxsZSBBX2kgXFxsZSAxMF45JCkuJm5ic3A7JEFfaSQmbmJzcDtyZXByZXNlbnRzIHRoZSB3ZWlnaHQgb2Ygc3RvbmUmbmJzcDskaSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIHNjb3JlIHRoYXQgY2FuIGJlIG9idGFpbmVkIGlmIHlvdSB0YWtlIHRoZSBzdG9uZXMgb3B0aW1hbGx5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=