34894번 - 간판 만들기

문제

UOSPC를 홍보하기 위해, 로비에 LED 문자 모듈을 일렬로 이어 붙인 전광판을 설치했다. 전광판의 모듈은 왼쪽부터 순서대로 총 $N$개이며, $i$번째 모듈이 표시할 수 있는 문자는 $S_i$이며 $S_i$는 U, O, S, P, C 중 하나이다.

이 중 일부 모듈만 켜서 UOSPC 문구를 만들 것이다. 이때 모듈의 순서는 바꿀 수 없으며 $i$번째 모듈을 킬 때 $a_i$만큼의 비용이 든다.

UOSPC를 표시하기 위한 총 비용의 최솟값을 구해보자. 구체적으로, $S_{i_1}=$U, $ S_{i_2}=$O, $S_{i_3}=$S, $S_{i_4}=$P, $S_{i_5}=$C, 1ドル\leq i_1<i_2<i_3<i_4<i_5 \leq N$인 $i_1, i_2, i_3, i_4, i_5$에 대해 $a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}+a_{i_5}$의 최솟값을 구하는것과 같다. 만들 수 없다면 -1을 출력한다.

입력

첫째 줄에 정수 $N$이 주어진다. $(5\leq N \leq 300,000円)$

둘째 줄에 U, O, S, P, C로만 이뤄진 문자열 $S$가 주어진다. $(|S|=N)$

셋째 줄에 $a_1, a_2, \cdots , a_N$가 공백으로 구분되어 주어진다. $(1\leq a_i \leq 10^9)$

출력

첫째 줄에 비용의 최솟값을 출력한다. 만약 문구를 만드는 것이 불가능하다면 -1을 출력한다.

제한

노트