题目描述

Kyusho 上一次给选手安排房间时表现得不太好，于是他决定再试一次。这次他认为，最好让参赛者彼此多认识一些人，所以他希望每个房间中来自不同城市的人尽可能多。

共有 $N$ 名参赛者，编号为 $1$ 到 $N$。第 $i$ 名参赛者来自城市 $c_i$。

这些参赛者需要被安排到 $K$ 个房间中。由于所有人已经在前台排好队，Kyusho 决定不改变他们的相对顺序：他会把前 $T_1$ 人安排到第一个房间，把接下来的 $T_2$ 人安排到第二个房间，依此类推，直到把最后 $T_K$ 人安排到第 $K$ 个房间。

注意，必须满足：

并且每个房间至少有一人，即 $T_i\ge 1$。

第 $i$ 个房间的熟识度 $F_i$ 定义为这个房间中参赛者来自的不同城市数量。

Kyusho 希望最大化

请编写程序 hotel，求出这个最大值。

输入格式

第一行包含两个正整数 $N,K$，分别表示参赛者数量和房间数量。

第二行包含 $N$ 个整数 $c_i$，表示每名参赛者来自的城市。

输出格式

输出一行一个整数，表示 $F_1+F_2+\cdots+F_K$ 的最大可能值。

数据范围

• $1\le N\le 5000$；
• $1\le K\le \min(N,500)$；
• $1\le c_i\le N$。

子任务

某个子任务得分，要求通过该子任务中的所有测试点。

样例 1

输入

4 1
1 2 2 1

输出

2

解释

取 $T_1=4$。

样例 2

输入

7 2
1 3 3 1 4 4 4

输出

5

解释

一种最优划分为 $T_1=2,T_2=5$。

样例 3

输入

8 3
7 7 8 7 7 8 1 7

输出

6

解释

一种最优划分为 $T_1=3,T_2=3,T_3=2$。