Массив \(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\) подмассивов в разбиении является наибольшей возможной.
Выходные данные
В первой строке выведите наибольшую возможную сумму симпатичностей подмассивов в разбиении.
Во второй строке выведите \(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\)-й подмассив.
В случае если есть несколько оптимальных разбиений, выведите любое из них.
Примечание
В первом примере одно из оптимальных разбиений выглядит как \([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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 2 3
5 2 5 2 4 1 1 3 2
|
21
3 5
|
|
2
|
6 1 4
4 1 3 2 2 3
|
12
1 3 5
|
|
3
|
2 1 2
-1000000000 1000000000
|
0
1
|