C. Earth
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Warith has been coping for a while about not being able to see Le Sserafim in Dallas, so he decided to take a mental break. He decided to go down to the Colorado River and skip some stones. When he arrived, he found $$$n$$$ stones arranged in a line. Warith knows that each stone has some mass $$$a_i$$$ $$$(1 \le i \le n)$$$. With all the stuff on his mind, he wants to maximize his enjoyment from skipping stones by picking a contiguous subarray $$$a'$$$ of the original stone array. Note that Warith cannot rearrange the stones, he can only pick a contiguous subarray from the original order.

For an array $$$a'$$$, the enjoyment from skipping all these stones is calculated as follows:

  • For each unique mass $$$m$$$ in the stones of $$$a'$$$, find the number of stones with this mass ($$$f$$$)
  • The enjoyment is the sum of $$$m \cdot f$$$ across all unique $$$m$$$

The only issue is that Warith also does not want the mass of the stones to vary too much either. Specifically, he doesn't want his subarray to contain more than $$$k$$$ distinct masses. With this in mind, can you help Warith maximize his enjoyment?

Input

The first line of input will contain two integers $$$n$$$ ($$$1 \le n \le 10^5$$$) and $$$k$$$ ($$$1 \le k \le n$$$): the number of stones, and the max number of permitted unique masses.

The second line contains $$$n$$$ integers ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the mass of the $$$i$$$th stone.

Output

Output a single integer $$$E$$$: the maximum enjoyment Warith can achieve.

Example
Input
8 3
1 7 2 3 2 2 1 7
Output
16
Note

In the sample test case, the optimal range is $$$[7, 2, 3, 2, 2]$$$, which has enjoyment $$$(7)(1) + (3)(1) + (2)(3) = 16$$$.