It's Mooin' Time

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

요약

L이 3 이하일 때, M과 그 뒤 L-1개의 O로 이루어진 부분 문자열을 k개 이상 포함하도록 문자열을 고치는 최소 비용을 모든 k에 대해 구한다.

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

문제

Bessie has a string of length $N$ ( $1\le N\le 3\cdot 10^5$ ) consisting solely of the characters M and O. For each position $i$ of the string, there is a cost $c\_i$ to change the character at that position to the other character ( $1\le c\_i\le 10^8$ ).

Bessie thinks the string will look better if it contains more moos of length $L$ ( $1\le L\le \min(N, 3)$ ). A moo of length $L$ is an M followed by $L-1$ Os.

For each positive integer $k$ from $1$ to $\lfloor N/L\rfloor$ inclusive, compute the minimum cost to change the string to contain at least $k$ substrings equal to a moo of length $L$ .

입력

The first line contains $L$ and $N$ .

The next line contains Bessie's length- $N$ string, consisting solely of Ms and Os.

The next line contains space-separated integers $c\_1\dots c\_N$ .

출력

Output $\lfloor N/L\rfloor$ lines, the answer for each $k$ in increasing order.

예제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

예상 출력