可爱子序列

题目描述

给定一个由 $n$ 个正整数组成的数组 $a_1, a_2, \ldots, a_n$ ，以及一个正整数 $k$ 。
你需要将数组划分为 $k$ 个非空子序列，使得数组中的每个元素恰好属于一个子序列。
子序列是指通过删除某些元素（不改变剩余元素的顺序）从另一个序列中得到的序列。

设第 $i$ 个子序列包含的元素下标为 $j_1 < j_2 < \ldots < j_l$ 。
该子序列的值定义为：

\max_{m=1}^{l} (a_{j_m} + m)

将数组划分为 $k$ 个子序列的代价等于这些子序列的值之和。

请你求出划分的最大代价。

第一行包含两个正整数 $n$ 和 $k$ （ $1 \le k \le n \le 500\,000$ ）——数组的长度以及需要划分成的子序列个数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le 10^9$ ）——数组中的元素。

输出一个整数——将给定数组划分为 $k$ 个非空子序列所能获得的最大代价。

5 3
3 7 10 1 2

在示例中，可以将数组划分为：
$[3, 10]$ ， $[7]$ ， $[1, 2]$ 。
则答案为：

子序列 $[3, 10]$ ： $m = 1$ 时 $a_{j_1} + 1 = 3 + 1 = 4$ ， $m = 2$ 时 $a_{j_2} + 2 = 10 + 2 = 12$ ，最大值 $12$ 。
子序列 $[7]$ ： $m = 1$ 时 $7 + 1 = 8$ ，最大值 $8$ 。
子序列 $[1, 2]$ ： $m = 1$ 时 $1 + 1 = 2$ ， $m = 2$ 时 $2 + 2 = 4$ ，最大值 $4$ 。

总代价 $12 + 8 + 4 = 24$ 。

测试数据分为 $6$ 组。只有通过某组的所有测试以及它所依赖的前若干组的所有测试，才能获得该组分数。