페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8189
서브태스크

It's Mooin' Time 3초 1024MB

문제

Bessie has a string of length N (1≤N≤3⋅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≤c_i≤10^8).

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

For each positive integer k from 1 to ⌊N/L⌋ 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…c_N.


출력

Output ⌊N/L⌋ lines, the answer for each k in increasing order.


부분문제

번호 점수 조건
#110점

L=3, N\le5,000

#220점

L=1

#330점

L=2

#440점

L=3


예제1

입력
14
MOOO
10203040
출력
0
20
50
90

예제2

입력
34
OOOO
50403020
출력
40

예제3

입력
220
OOOMOMOOOMOOOMMMOMOO
4474360239649528940281175081178097338107304268469490980722669835784987821800427816633124247112349054288888490759128511857458928954413775211846269768892810497142
출력
0
0
0
0
0
12851185
35521020
60232254
99881782
952304708

예제4

입력
320
OOOMOMOOOMOOOMMMOMOO
4474360239649528940281175081178097338107304268469490980722669835784987821800427816633124247112349054288888490759128511857458928954413775211846269768892810497142
출력
0
0
0
44743602
119332891
207066974

출처

USACO 2024 December Platinum

역링크