33054번 - It's Mooin' Time 다국어

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.