Sum of Few

We are given a sequence consisting of N positive integers ~\mathbf{x_1,x_2<\ldots,x_N}~ and a natural number K ~\le~ N. We select a contiguous interval of the sequence, let's say the numbers ~\mathbf{x_i,x_{i+1},\ldots,x_j}~ (for i ~\le~ j), within which no more than K different numbers appear, and sum them. What is the maximum sum we can achieve in this way?

Problem:

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the values of N and K, as well as the sequence of numbers, and prints the answer to the above question.

Input Files:

The input file named sumoffew.in is a text file with the following structure. The first line contains two integers N and K, separated by a single space. The number N represents the number of numbers in the sequence, while the number K represents the maximum allowed number of different numbers in the interval we will choose. The next line contains N positive integers, separated in pairs by a single space: the terms of the sequence.

Output Files:

The output file named sumoffew.out is a text file containing only one line with one integer: the answer to the above question.

Examples of Input - Output Files:

1o

STDIN (sumoffew.in)

10 1
9 5 5 5 5 5 9 9 9 17

STDOUT (sumoffew.out)

27

Explanation:Since K=1, we are looking for the interval consisting of consecutive appearances of the same number, which has the maximum sum. The three consecutive 9s yield a sum of 27, and that is the answer here.

2o

STDIN (sumoffew.in)

10 3
11 17 12 12 17 1 12 19 18 1

STDOUT (sumoffew.out)

71

Explanation: Here K=3. In the interval 17, 12, 12, 17, 1, 12, only three different numbers appear (1, 12, 17). The sum is 17+12+12+17+1+12=71. There is no other interval with at most three different numbers and a larger sum.

3o

STDIN (sumoffew.in)

7 4
1 6 3 8 2 4 7

STDOUT (sumoffew.out)

21

4o

STDIN (sumoffew.in)

9 4 
1 2 3 2 3 1 3 1 2

STDOUT (sumoffew.out)

18

Constraints:

• 1 ~\le~ K ~\le~ Ν ~\le~ 1.000.000
• The sum of all xi will not exceed 1.000.000.000
• For test cases worth 10% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 1000 and K = 1
• For test cases worth 50% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 1000, meaning the sequence will be relatively small.
• For test cases worth 70% of the total points, it will be:
  ~\mathbf{x_i}~ ~\le~ 1.000.000, meaning the terms of the sequence will be relatively small.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.
Headers in the source code: At the beginning of your source code, you should use the following headers

(* USER: username
LANG: PASCAL
TASK: sumoffew *)

for PASCAL coders

/* USER: username
LANG: C
TASK: sumoffew */

for C coders

/* USER: username
LANG: C++
TASK: sumoffew */

for C++ coders

/* USER: username
LANG: Java
TASK: sumoffew */

for Java coders

# USER: username
# LANG: Python
# TASK: sumoffew

for Python coders