Description

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

子序列是指通过从原数组删除一些元素（不改变剩余元素的顺序）所获得的序列。

设第 $i$ 个子序列包含的元素索引为 $j_1 < j_2 < \dots < j_l$。则这个子序列的价值定义为所有 $1 \leq m \leq l$ 中的最大值 $a_{j_m} + m$。

数组划分成 $k$ 个子序列的花费（cost）定义为所有子序列的价值之和。

你的任务是计算出划分方案的最大花费。

Format

Input

第一行包含两个正整数 $n$ 和 $k$（$1 \leq k \leq n \leq 500000$），分别表示数组的长度以及要划分的子序列个数。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组元素。

Output

输出一个整数，表示将数组划分成 $k$ 个非空子序列所能得到的最大花费。

Samples

5 3
3 7 10 1 2

24

Note

在样例中，一个最优划分方案为子序列：[3,10], [7], [1,2]。
各子序列的价值分别为：(10+2), (7+1), (2+2)，因此总花费为 12 + 8 + 4 = 24。