题目描述
有一个长度为 $n$ 的序列 $a$。
设一个区间的价值为此区间的 $\operatorname{mex}$ 值乘上区间元素总和。其中 $\operatorname{mex}$ 值定义为该集合中不属于集合的最小非负整数，例如 $\operatorname{mex}(0,1,3,5)=2$。
你需要将数组划分成若干非空区间，其中每个区间的长度不超过 $k$。一个划分方案的价值为每个区间的价值之和。
你需要找到满足题意的划分方案下的最大价值。
输入格式
第一行包含两个整数：$n,k$，表示数组的长度、子数组长度的上限。
第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$（$0 \leq a_i \leq n$）。
输出格式
输出一个非负整数，表示最大的价值。
样例输入 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
样例 4/5
见下发文件。
数据范围
对于全部数据，满足 $2\le n\le 2\times 10^5,1\le k\le n,0\le a_i\le n$。
| 子任务编号 | $n\le $ | 特殊性质 | 分数 |
|---|---|---|---|
| 1 | $10$ | 无 | 4 |
| 2 | $5000$ | 无 | 8 |
| 3 | $2\times 10^4$ | 无 | 8 |
| 4 | $2\times 10^5$ | A | 24 |
| 5 | $2\times 10^5$ | B | 20 |
| 6 | $1\times 10^5$ | 无 | 16 |
| 7 | $2\times 10^5$ | 无 | 20 |
特殊性质 A：$a_i\le 10$。
特殊性质 B：数据满足在 $a_i$ 在 $[0,n]$ 内随机生成。