给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。你需要找到一种最优的划分方式，将该数组划分为若干个长度不超过 $k$ 的连续子数组，以最大化你的总利润。一个子数组的利润定义为该子数组中所有元素的和乘以该子数组的 $mex$ 值。总利润为所有子数组利润之和。

我们定义一个非负整数集合的 $mex$ 值为不属于该集合的最小非负整数。例如：$mex(0, 1, 3) = 2$。

输入格式

第一行包含两个整数：$n$ ($2 \le n \le 200\,000$)，表示数组的长度；$k$ ($1 \le k \le n$)，表示子数组长度的上限。

第二行包含 $n$ 个整数，表示数组的元素：第 $i$ 个整数为 $a_i$，$0 \le a_i \le n$。

输出格式

输出一个非负整数：将给定数组划分为长度不超过 $k$ 的子数组所能获得的最大总利润。

样例

输入 1

5 3
3 4 0 0 3

输出 1

10

输入 2

8 4
0 1 2 0 3 1 4 1

输出 2

26

输入 3

10 5
0 2 0 1 2 1 0 2 2 1

输出 3

33