[AdditionalFile5356.zip](file://AdditionalFile5356.zip?type=additional_file)

#5356. 「OOI 2025 Day 1」可爱的子序列

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2025 Day1 T4 「Милые подпоследовательности / Cute Subsequences」。

给定一个包含 $n$ 个正整数的数组 $a_1, a_2, \ldots, a_n$，以及一个正整数 $k$。你需要将这个数组分成 $k$ 个非空的子序列，使得数组中的每个元素恰好属于一个子序列。子序列是指通过从原序列中删除某些元素（不改变剩余元素的顺序）所得到的序列。

假设第 $i$ 个子序列包含编号为 $j_1 < \ldots < j_l$ 的元素。该子序列的价值定义为对所有 $m$（从 $1$ 到 $l$）取 $a_{j_m} + m$ 的最大值。

将数组分成 $k$ 个子序列的成本定义为这 $k$ 个子序列价值的总和。

请找出最大的成本。

输入格式

第一行包含两个正整数 $n$ 和 $k$ $(1 \leq k \leq n \leq 500000)$，分别表示数组的大小和需要分成的子序列数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^{9})$，表示数组的元素。

输出格式

输出一个整数，即将给定数组分成 $k$ 个非空子序列的最大成本。

样例

输入

5 3
3 7 10 1 2

输出

24

在样例中，数组可以分成 $[3, 10]$、$[7]$ 和 $[1, 2]$。此时，答案为 $(10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。