B. Очередная задача про разбиение массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$b$$$ называется подмассивом массива $$$a$$$, если он образует непрерывный подотрезок $$$a$$$, то есть равен $$$a_l$$$, $$$a_{l + 1}$$$, $$$\ldots$$$, $$$a_r$$$ для некоторых $$$l, r$$$.

Пусть $$$m$$$ — некоторая зафиксированная константа. Для любого массива, содержащего хотя бы $$$m$$$ элементов, определим его симпатичность, как сумму $$$m$$$ наибольших элементов этого массива. Например:

  • Если массив $$$x = [4, 3, 1, 5, 2]$$$ и $$$m = 3$$$, то $$$3$$$ наибольших элемента $$$x$$$ равны $$$5$$$, $$$4$$$ и $$$3$$$, тем самым симпатичность $$$x$$$ равна $$$5 + 4 + 3 = 12$$$.
  • Если массив $$$x = [10, 10, 10]$$$ и $$$m = 2$$$, то симпатичность $$$x$$$ равна $$$10 + 10 = 20$$$.

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$, значение константы $$$m$$$ и целое число $$$k$$$. Вам нужно разбить массив $$$a$$$ на ровно $$$k$$$ подмассивов таких, что:

  • Каждый элемент $$$a$$$ принадлежит ровно одному подмассиву.
  • Каждый подмассив содержит хотя бы $$$m$$$ элементов.
  • Суммарная симпатичность всех $$$k$$$ подмассивов в разбиении является наибольшей возможной.
Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m$$$, $$$2 \le k$$$, $$$m \cdot k \le n$$$) — количество элементов в $$$a$$$, константа $$$m$$$ в условии и количество подмассивов, на которые нужно разбить.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Выходные данные

В первой строке выведите наибольшую возможную сумму симпатичностей подмассивов в разбиении.

Во второй строке выведите $$$k-1$$$ целых чисел $$$p_1, p_2, \ldots, p_{k-1}$$$ ($$$1 \le p_1 < p_2 < \ldots < p_{k-1} < n$$$) определяющих разбиение массива.

  • В первый подмассив попадают элементы с индексами от $$$1$$$ до $$$p_1$$$.
  • Во второй подмассив попадают элементы с индексами от $$$p_1 + 1$$$ до $$$p_2$$$.
  • $$$\ldots$$$.
  • Все элементы с индексами от $$$p_{k-1} + 1$$$ до $$$n$$$ попадают в последний, $$$k$$$-й подмассив.

В случае если есть несколько оптимальных разбиений, выведите любое из них.

Примеры
Входные данные
9 2 3
5 2 5 2 4 1 1 3 2
Выходные данные
21
3 5
Входные данные
6 1 4
4 1 3 2 2 3
Выходные данные
12
1 3 5
Входные данные
2 1 2
-1000000000 1000000000
Выходные данные
0
1
Примечание

В первом примере одно из оптимальных разбиений выглядит как $$$[5, 2, 5]$$$, $$$[2, 4]$$$, $$$[1, 1, 3, 2]$$$.

  • Симпатичность подмассива $$$[5, 2, 5]$$$ равна $$$5 + 5 = 10$$$.
  • Симпатичность подмассива $$$[2, 4]$$$ равна $$$2 + 4 = 6$$$.
  • Симпатичность подмассива $$$[1, 1, 3, 2]$$$ равна $$$3 + 2 = 5$$$.

Таким образом, суммарная симпатичность равна $$$10 + 6 + 5 = 21$$$.

Во втором примере одно из оптимальных разбиений выглядит как $$$[4]$$$, $$$[1, 3]$$$, $$$[2, 2]$$$, $$$[3]$$$.