베시는 길이가 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를 포함하게 하기 위해 필요한 비용을 계산하자.

It's Mooin' Time timer 3s memory 1024MB

It's Mooin' Time 3s 1024MB