Description

给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \ldots, a_n$，以及一个正整数 $k$。你需要将该数组划分为 $k$ 个非空子序列，使得每个元素恰好属于一个子序列。

子序列指的是从原始序列中删除若干个元素（可以为零），但不改变剩余元素的相对顺序后所得到的序列。

设第 $i$ 个子序列包含的是原数组中下标为 $j_1 < \ldots < j_l$ 的元素。该子序列的「价值」定义为 $\max\limits_{1 \le m \le l}(a_{j_m} + m)$。

将数组划分为 $k$ 个子序列的「代价」是这 $k$ 个子序列的价值之和。

请你计算出数组在划分方案最优时所能获得的最大代价。

Input Format

第一行包含两个正整数 $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$）—— 表示数组中的元素。

Output Format

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

5 3
3 7 10 1 2

24

Hint

样例解释

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

本题的测试点共包含六个分组。只有当某个分组的所有测试点以及其依赖的所有分组测试点均通过时，才能获得该分组的分数。