**Замечание: Время на тест для этой задачи 3 сек, в 1.5 больше
чем по умолчанию.**
У Беси есть строка длины \(N\) (\(1\le N\le 3\cdot 10^5\)) состоящая только
из символов M и O. Для каждой позиции \(i\) в этой строке есть цена замены
(\(1\le c_i\le 10^8\)) этого символа на другой.
Беси думает, что строка будет выглядеть лучше, если она будет содержать
больше moo длиной \(L\) (\(1\le L\le \min(N, 3)\)). Moo длиной \(L\) is
символ M за которым следуют \(L-1\) символов O.
Для каждого положительного целого \(k\) от \(1\) до \(\lfloor N/L\rfloor\)
включительно, вычислите минимальную стоимость изменить строк так,
чтобы она содержала как минимум \(k\) подстрок равных moo длины \(L\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(L\) и
\(N\).
Следующая строка содержит строку Беси длиной \(N\), состоящую только из
символов M и O.
Следующая строка содержит разделённые одиночными пробелами целые числа
\(c_1\dots c_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(\lfloor N/L\rfloor\) строк, ответов для каждого \(k\)
в порядке возрастания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 4
MOOO
10 20 30 40
|
0
20
50
90
|