There is a sequence $a$ of length $n$.
The value of an interval is defined as the product of the $\operatorname{mex}$ of the interval and the sum of the elements in the interval. The $\operatorname{mex}$ of a set is defined as the smallest non-negative integer that is not present in the set. For example, $\operatorname{mex}(0, 1, 3, 5) = 2$.
You need to partition the array into several non-empty intervals, where the length of each interval does not exceed $k$. The value of a partition is the sum of the values of each interval.
You need to find the maximum value among all valid partitions.
Input
The first line contains two integers: $n$ and $k$, representing the length of the array and the upper bound on the length of each sub-array.
The second line contains $n$ integers, where the $i$-th integer is $a_i$ ($0 \leq a_i \leq n$).
Output
Output a non-negative integer representing the maximum value.
Examples
Input 1
5 3 3 4 0 0 3
Output 1
10
Input 2
8 4 0 1 2 0 3 1 4 1
Output 2
26
Input 3
10 5 0 2 0 1 2 1 0 2 2 1
Output 3
33
Input 4
See provided files.
Output 4
See provided files.
Constraints
For all data, $2 \le n \le 2\times 10^5$, $1 \le k \le n$, $0 \le a_i \le n$.
| Subtask ID | $n \le$ | Special Property | Score |
|---|---|---|---|
| 1 | $10$ | None | 4 |
| 2 | $5000$ | None | 8 |
| 3 | $2\times 10^4$ | None | 8 |
| 4 | $2\times 10^5$ | A | 24 |
| 5 | $2\times 10^5$ | B | 20 |
| 6 | $1\times 10^5$ | None | 16 |
| 7 | $2\times 10^5$ | None | 20 |
Special Property A: $a_i \le 10$.
Special Property B: The data is generated such that $a_i$ is uniformly random in $[0, n]$.