You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

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

题目描述

现在有一个序列 $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$。