题目背景

娃儿些过的太好 不晓得生活的重

年纪轻轻谈儿女情长有鸡儿的用

我不怕飞得不够高也不怕跩得痛

我只怕自己当个白痴白痴不敢做梦

题目描述

现在有一个序列 $a$，需要分成 $k$ 个子序列。

对于分割出来的每一个子序列，设 $len_i$ 为第 $i$ 个子序列的长度，其权值为 $\max\limits_{j=1}^{len_i} (b_{i,j}+j)$，其中 $b_{i,j}$ 表示第 $i$ 个子序列的第 $j$ 个元素的值。

现在请你按照一种合理的分割顺序，使得分割出来的子序列权值总和最大。

输入格式

第一行两个整数 $n,k$。

接下来一行 $n$ 个整数，表示原序列。

输出格式

一行一个整数，表示最大的代价总和。

5 3
7 2 9 2 10

31

样例解释

能分割出31的方案有很多，一种可行的分割方案是，把序列分割成 $[7],[9],[2,2,10]$，答案为 $8+10+13 = 31$,或者分割成 $[7],[2,9],[2,10]$,$8+11+12 = 31$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le k\le n \le 10^6, 1\le a_i \le 10^9$。