Test tubes

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The rumor that Zenik is an awesome programmer quickly spread throughout the university. Therefore, students and sometimes even professors from other faculties often started coming to him with requests for various kinds of help.

So, one day, a laboratory assistant from the Department of Inorganic Chemistry knocked on Zenik’s dorm room. In his hands, he had \(n\) numbered test tubes with reagents. In the \(i\)-th test tube, there is a substance \(a_i\), for simplicity, we will denote substances by integers.

Note that different test tubes may contain the same substances.

To conduct the laboratory work, the lab assistant needs to distribute all \(n\) test tubes among \(k\) students such that each student receives some contiguous set of test tubes (i.e., a set of test tubes with consecutive numbers, for example from 4 to 7). A student’s satisfaction from performing the laboratory work is equal to the number of distinct substances in the test tubes they received.

Since the lab assistant conscientiously does his job and is a true promoter of chemistry, he wants to maximize the total satisfaction that the students will get from performing his laboratory work.

Zenik is too busy with more important things than students’ satisfaction from lab works, so he passes this task on to you.

Input

The first line contains two integers \(n\) and \(k\) separated by a space — the number of test tubes and the number of students.

The next line contains \(n\) integers \(a_i\) — the substance in the \(i\)-th test tube.

Output

In a single line, print one integer — the maximum total satisfaction level of the students.

Constraints

\(1 \leq n \leq 5000\),

\(1 \leq k \leq 100\),

\(1 \leq a_i \leq 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 4 7 4 1 2 4 2	7

Notes

For example, the first student can get the first and second test tubes, the second — the third, the third — the fourth and fifth, and the fourth — the rest. Then the total satisfaction will be equal to \(2+1+2+2=7\).