37th Petrozavodsk Programming Camp, Summer 2019 Day 9：MEX Foundation Contest（2019-09-02） 时间限制：4 秒，内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。你需要把整个数组划分成若干个连续子数组（即分段覆盖、每个元素恰好属于一个段），并要求每个子数组长度不超过 $k$，使得总收益最大。

对于一个子数组，其收益定义为：

$$(\text{子数组元素之和}) \times \mathrm{mex}(\text{该子数组的元素集合})$$

总收益为所有子数组收益之和。

mex 的定义

对一组非负整数，$\mathrm{mex}$ 定义为不在这组数中出现的最小非负整数。例如：

$$\mathrm{mex}({0,1,3}) = 2$$

---

输入格式

• 第一行两个整数 $n, k$：数组长度与子数组长度上限。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

---

输出格式

输出一个非负整数：在子数组长度均不超过 (k) 的前提下，能够获得的最大总收益。

---

数据范围

• $2 \le n \le 200000$
• $1 \le k \le n$
• $0 \le a_i \le n$

---

样例

样例 1

输入：

5 3
3 4 0 0 3

输出：

10

样例 2

输入：

8 4
0 1 2 0 3 1 4 1

输出：

26

样例 3

输入：

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

输出：

33

---

部分分设计（100 分）

子任务	分值	额外限制
1	10	$n \le 2000$
2	15	$k \le 20$
3	20	$a_i \le 20$
4	25	$n \le 50000$
5	30	无额外限制