Lưu ý: Giới hạn thời gian của bài này là 3 giây, gấp 1,5 lần mức mặc định.

Bessie có một xâu độ dài \(N\) (\(1\leq N\leq 3\cdot 10^5\)) chỉ gồm các ký tự M và O. Với mỗi vị trí \(i\) của xâu, chi phí để đổi ký tự tại vị trí đó thành ký tự còn lại là \(c_i\) (\(1\leq c_i\leq 10^8\)).

Bessie cho rằng xâu sẽ đẹp hơn nếu chứa nhiều tiếng moo độ dài \(L\) (\(1\leq L\leq\min(N,3)\)). Một tiếng moo độ dài \(L\) là một ký tự M theo sau bởi \(L-1\) ký tự O.

Với mỗi số nguyên dương \(k\) từ \(1\) đến \(\lfloor N/L\rfloor\), hãy tính chi phí nhỏ nhất để thay đổi xâu sao cho nó chứa ít nhất \(k\) xâu con bằng một tiếng moo độ dài \(L\).

Dữ liệu vào

Dòng đầu chứa \(L\) và \(N\).

Dòng tiếp theo chứa xâu độ dài \(N\) của Bessie, chỉ gồm các ký tự M và O.

Dòng tiếp theo chứa các số nguyên cách nhau bởi dấu cách \(c_1\dots c_N\).

Dữ liệu ra

In \(\lfloor N/L\rfloor\) dòng, lần lượt là đáp án cho từng \(k\) theo thứ tự tăng dần.

Phân nhóm

• Test 5: \(L=3\), \(N\leq 5000\).
• Test 6: \(L=1\).
• Các test 7–10: \(L=2\).
• Các test 11–18: \(L=3\).

Ví dụ

1 4
MOOO
10 20 30 40

0
20
50
90

3 4
OOOO
50 40 30 20

40

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

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

Nguồn

Đề bài gốc: USACO 2024 December Contest, Platinum — It's Mooin' Time

Tác giả: Benjamin Qi.