Ahmet has planted \(\mathbf{N}\) trees in a line. The type of k-th tree is \(\mathbf{T_k}\). Ozan wants to create \(\mathbf{M}\) gardens by building \(\mathbf{M} - 1\) walls between the trees so that the tree line is splitted into \(\mathbf{M}\) line segments each being a separate garden. Note that some gardens may contain no tree.

"Beauty" of a garden is equal to the number of distinct tree types in it. What is the maximal possible total "beauty" of the gardens?

Input

The first line contains two integers \(\mathbf{N}\) and \(\mathbf{M}\) separated by a single space. The next line contains \(\mathbf{N}\) integers \(\mathbf{T_1}, \ldots, \mathbf{T_N}\) separated by single spaces.

Output

The maximal possible total garden "beauty".

Constraints

• \(1 <= \mathbf{N} <= 5000\),
• \(1 <= \mathbf{M} <= 100\),
• \(1 <= \mathbf{T_k} <= 10^9\).

Example

Input

7 4
4 7 4 1 2 4 2

Output

7

Notes

In the sample one of the optimal solutions is to form the following gardens:

• the first and the second trees;
• the third tree;
• the fourth and the fifth trees;
• the sixth and the seventh trees. Then the overall "beauty" is \(2+1+2+2=7\).