Yet Another Mex Problem

Time limit4sMemory limit512 MB

Summary

Split an array into contiguous pieces of length at most k to maximize the sum of each piece's elements times its mex, and print the total.

Level: Hard8 of 10
Topics: Dynamic programming, Array, Segment tree
Solved: No attempts yet

Problem

You are given an array a of length n and an integer k. Divide the array into contiguous subarrays, each with length at most k, so that the total profit is maximized. The profit of one subarray is the sum of its elements multiplied by the mex of that subarray. The total profit is the sum of the profits of all subarrays.

The mex of a set of non-negative integers is the smallest non-negative integer that does not belong to the set. For example, mex(0, 1, 3) = 2.

Input

The first line contains two integers n (2 ≤ n ≤ 200 000), the length of the array, and k (1 ≤ k ≤ n), the upper bound on the subarray length.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ n).

Output

Print one non-negative integer: the maximum total profit over all divisions of the array into subarrays of length at most k.

Examples3

Example 1
Input
```
5 3
3 4 0 0 3
```
Expected output
```
10
```
Example 2
Input
```
8 4
0 1 2 0 3 1 4 1
```
Expected output
```
26
```
Example 3
Input
```
10 5
0 2 0 1 2 1 0 2 2 1
```
Expected output
```
33
```