platinum_Its_Mooin_Time — USACO December_Contest
Task type: batch | Time limit: 3 s | Memory limit: 256 MB | Difficulty: 24
Algorithms: greedy, two pointers, divide and conquer, dynamic programming

**Note: The time limit for this problem is 3s, 1.5x the default.**
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$.
INPUT FORMAT (input arrives from the terminal / stdin):
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 FORMAT (print output to the terminal / stdout):
Output $\lfloor N/L\rfloor$ lines, the answer for each $k$ in increasing order.
SAMPLE INPUT:
1 4
MOOO
10 20 30 40
SAMPLE OUTPUT:
0
20
50
90
SAMPLE INPUT:
3 4
OOOO
50 40 30 20
SAMPLE OUTPUT:
40
SAMPLE INPUT:
2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142
SAMPLE OUTPUT:
0
0
0
0
0
12851185
35521020
60232254
99881782
952304708
SAMPLE INPUT:
3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142
SAMPLE OUTPUT:
0
0
0
44743602
119332891
207066974
SCORING:
Input 5: $L=3, N\le 5000$
Input 6: $L=1$
Inputs 7-10: $L=2$
Inputs 11-18: $L=3$
Problem credits: Benjamin Qi

Starter code: