CF1114B.Yet Another Array Partitioning Task

An array $b$ is called to be a subarray of $a$ if it forms a continuous subsequence of $a$, that is, if it is equal to $a_l$, $a_{l + 1}$, $\ldots$, $a_r$ for some $l, r$.

Suppose $m$ is some known constant. For any array, having $m$ or more elements, let's define it's beauty as the sum of $m$ largest elements of that array. For example:

• For array $x = [4, 3, 1, 5, 2]$ and $m = 3$, the $3$ largest elements of $x$ are $5$, $4$ and $3$, so the beauty of $x$ is $5 + 4 + 3 = 12$.
• For array $x = [10, 10, 10]$ and $m = 2$, the beauty of $x$ is $10 + 10 = 20$.

You are given an array $a_1, a_2, \ldots, a_n$, the value of the said constant $m$ and an integer $k$. Your need to split the array $a$ into exactly $k$ subarrays such that:

• Each element from $a$ belongs to exactly one subarray.
• Each subarray has at least $m$ elements.
• The sum of all beauties of $k$ subarrays is maximum possible.

数组 $b$ 被称为数组 $a$ 的子数组，当且仅当它是 $a$ 的一个连续子序列，即存在某个 $l, r$，使得 $b = a_l, a_{l + 1}, \ldots, a_r$。

设 $m$ 是某个已知常数。对于任意长度不小于 $m$ 的数组，我们定义其**美丽值（beauty）**为该数组中最大的 $m$ 个元素之和。例如：

• 对于数组 $x = [4, 3, 1, 5, 2]$ 和 $m = 3$，$x$ 中最大的 $3$ 个元素是 $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$ 个子数组的美丽值之和达到最大可能值。

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m$, $2 \le k$, $m \cdot k \le n$) — the number of elements in $a$, the constant $m$ in the definition of beauty and the number of subarrays to split to.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

第一行包含三个整数 $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$）。

In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.

In the second line, print $k-1$ integers $p_1, p_2, \ldots, p_{k-1}$ ($1 \le p_1 \lt p_2 \lt \ldots \lt p_{k-1} \lt n$) representing the partition of the array, in which:

• All elements with indices from $1$ to $p_1$ belong to the first subarray.
• All elements with indices from $p_1 + 1$ to $p_2$ belong to the second subarray.
• $\ldots$.
• All elements with indices from $p_{k-1} + 1$ to $n$ belong to the last, $k$-th subarray.

If there are several optimal partitions, print any of them.

第一行输出最优划分下所有子数组的美丽值之和的最大可能值。

第二行输出 $k-1$ 个整数 $p_1, p_2, \ldots, p_{k-1}$（满足 $1 \le p_1 \lt p_2 \lt \ldots \lt p_{k-1} \lt n$），表示该数组的一种划分，其中：

• 下标从 $1$ 到 $p_1$ 的所有元素属于第一个子数组；
• 下标从 $p_1 + 1$ 到 $p_2$ 的所有元素属于第二个子数组；
• $\ldots$；
• 下标从 $p_{k-1} + 1$ 到 $n$ 的所有元素属于最后一个（即第 $k$ 个）子数组。

若存在多种最优划分，输出任意一种即可。

In the first example, one of the optimal partitions is $[5, 2, 5]$, $[2, 4]$, $[1, 1, 3, 2]$.

• The beauty of the subarray $[5, 2, 5]$ is $5 + 5 = 10$.
• The beauty of the subarray $[2, 4]$ is $2 + 4 = 6$.
• The beauty of the subarray $[1, 1, 3, 2]$ is $3 + 2 = 5$.

The sum of their beauties is $10 + 6 + 5 = 21$.

In the second example, one optimal partition is $[4]$, $[1, 3]$, $[2, 2]$, $[3]$.

在第一个例子中，一种最优划分是 $[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]$。