Page not loading? Try clicking here.
Placeholder

#8189
Subtask

It's Mooin' Time 3s 1024MB

Problems

베시는 길이가 N (1≤N≤3⋅10^5) 인 문자열을 가지고 있고, 문자열은 오직 M 과 O 로만 이루어져 있다. 문자열의 각 위치 i 에 대해 비용 c_i 를 소모해 한 문자를 다른 문자로 바꿀 수 있다. (1≤c_i≤10^8).

베시는 문자열에 길이 L 의 moo를 많이 포함되면 보기 좋을 것이라고 생각한다. (1≤L≤min(N,3)). 길이 L 의 moo 는 하나의 M 과 L−1 개의 O 를 이은 문자열로 정의된다.

1 to ⌊N/L⌋ 까지의 양수 k 에 대해, 문자열이 적어도 k개의 길이 L인 moo를 포함하게 하기 위해 필요한 비용을 계산하자.


Input

첫 번째 줄에 L과 N이 공백으로 구분되어 주어진다..

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

세 번째 줄에 N개의 수 c_1…c_N이 공백으로 구분되어 주어진다.


Output

⌊N/L⌋ 개의 줄을 출력한다. k 번째 줄에 문자열이 적어도 k개의 길이 L인 moo를 포함하게 하기 위해 필요한 비용을 출력한다.


Subtask

# Score Condition
#110

L=3, N\le5,000

#220

L=1

#330

L=2

#440

L=3


Example #1

1 4
MOOO
10 20 30 40
0
20
50
90

Example #2

3 4
OOOO
50 40 30 20
40

Example #3

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

Example #4

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

Source

USACO 2024 December Platinum

You must sign in to write code.