给定一个包含 $n$ 个正整数的数组 $a_1, a_2, \dots, a_n$，以及一个正整数 $k$。你需要将该数组划分为 $k$ 个非空子序列，使得数组中的每个元素恰好属于其中一个子序列。子序列是指通过删除原序列中某些元素且不改变剩余元素相对顺序所得到的序列。
设第 $i$ 个子序列包含下标为 $j_1 < \dots < j_l$ 的元素。该子序列的价值定义为所有 $m$（$1 \le m \le l$）中 $a_{j_m} + m$ 的最大值。
将数组划分为 $k$ 个子序列的代价是这些子序列价值的总和。求划分的最大代价。
输入格式
第一行包含两个正整数 $n$ 和 $k$ ($1 \le k \le n \le 500\,000$)，分别表示数组的大小和需要划分成的子序列数量。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示数组的元素。
输出格式
输出将给定数组划分为 $k$ 个非空子序列的最大代价。
样例
样例输入 1
5 3 3 7 10 1 2
样例输出 1
24
说明
在样例测试中，数组可以划分为 $[3, 10], [7], [1, 2]$。此时答案为 $(10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24$。
子任务
本题的测试点分为六组。仅当通过某一组及其所有前置组的全部测试点时，才能获得该组的分数。
| 组别 | 分数 | $n$ | $k$ | 前置组 | 说明 |
|---|---|---|---|---|---|
| 0 | 0 | – | – | – | 样例 |
| 1 | 14 | $n \le 8$ | – | 0 | |
| 2 | 19 | – | $k = 2$ | – | |
| 3 | 17 | – | – | – | $a_{i+1} \le a_i$ |
| 4 | 21 | – | – | – | $a_{i+1} \ge a_i - 1$ |
| 5 | 15 | $n \le 1000$ | – | 0, 1 | |
| 6 | 14 | – | – | 0–5 |