题目描述

有一个长度为 $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$。

特殊性质 A：$a_i\le 10$。

特殊性质 B：数据满足在 $a_i$ 在 $[0,n]$ 内随机生成。