题目描述

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

给定一个含 $n$ 个正整数的数组 $a_1, a_2, \ldots, a_n$ 和正整数 $k$，需将数组分成 $k$ 个非空的子序列（每个元素恰好属于一个子序列，子序列保持原元素顺序）。

• 若第 $i$ 个子序列包含元素 $a_{j_1}, a_{j_2}, \ldots, a_{j_l}$（$j_1 < j_2 < \ldots < j_l$），其价值为 $\max_{1 \leq m \leq l} (a_{j_m} + m)$；
• 总分类成本为 $k$ 个子序列价值的总和。
  需找出最大的分类成本。

输入格式

1. 第一行：两个正整数 $n$ 和 $k$（$1 \leq k \leq n \leq 500000$），分别表示数组大小和子序列数量；
2. 第二行：$n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组元素。

输出格式

输出一个整数，即分成 $k$ 个子序列的最大成本。

样例

输入

5 3
3 7 10 1 2

输出

24