잇츠 무인 타임

시간 제한3초메모리 제한2048 MB

요약

M과 O로 이루어진 문자열과 각 위치를 뒤집는 비용이 주어질 때, 길이 L인 moo를 k개 이상 만드는 최소 비용을 모든 k에 대해 구합니다.

난이도: 보통10점 중 7점
유형: 그리디, 문자열, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Bessie에게 M과 O로만 이루어진 길이 $N$ 의 문자열이 있다 ( $1\le N\le 3\cdot 10^5$ ). 각 위치 $i$ 의 문자를 다른 문자로 바꾸는 비용은 $c_i$ 이다 ( $1\le c_i\le 10^8$ ).

Bessie는 길이 $L$ 인 moo를 문자열에 더 많이 넣고 싶어 한다 ( $1\le L\le \min(N, 3)$ ). 길이 $L$ 인 moo는 M 하나 뒤에 O가 $L-1$ 개 붙은 문자열이다.

양의 정수 $k$ 가 $1$ 부터 $\lfloor N/L\rfloor$ 까지일 때, 길이 $L$ 인 moo와 같은 부분 문자열을 적어도 $k$ 개 포함하도록 문자열을 바꾸는 최소 비용을 구하라.

입력

첫 번째 줄에 $L$ 과 $N$ 이 주어진다.

두 번째 줄에 M과 O로만 이루어진 길이 $N$ 의 문자열이 주어진다.

세 번째 줄에 공백으로 구분된 정수 $c_1 \dots c_N$ 이 주어진다.

출력

$\lfloor N/L\rfloor$ 개의 줄을 출력한다. $k$ 번째 줄에는 $k$ 에 대한 최소 비용을 $k$ 의 오름차순으로 출력한다.

예제4

예제 1
입력
```
1 4
MOOO
10 20 30 40
```
예상 출력
```
0
20
50
90
```
예제 2
입력
```
3 4
OOOO
50 40 30 20
```
예상 출력
```
40
```

예제 3

입력

2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

예상 출력

예제 4

입력

3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

예상 출력