一栋新的学生宿舍刚刚启用！它由 $M$ 栋楼组成，编号为 $1$ 到 $M$。宿舍起初是空的，但很快将有 $N$ 名学生搬进来，每天正好搬进一名学生。

每当有新学生搬进某栋楼时，那栋楼里就会举行一场盛大的派对。派对的噪音值等于当时该栋楼内的学生人数。宿舍管理人员非常讨厌噪音，因此他们偶尔会清空某栋楼，以将派对的噪音控制在合理的水平。他们通过将该栋楼内的所有住宿生转移到一所完全不同的学生宿舍来实现这一点。管理人员可以在任何一天结束后决定进行此操作，但他们意识到这样做总共不能超过 $K$ 次。

请帮助管理人员！已知每天学生搬入的宿舍楼编号，求在最多清空宿舍楼 $K$ 次的情况下，能够达到的最小可能总噪音值（所有 $N$ 场派对的噪音值之和）。

输入格式

输入的第一行包含三个整数 $N$ ($1 \le N \le 1\,000\,000$)，$M$ ($1 \le M \le 100$) 和 $K$ ($1 \le K \le 500$)，含义如题面所述。

接下来的 $N$ 行中，第 $i$ 行包含一个区间 $[1, M]$ 内的整数，表示第 $i$ 天搬入宿舍的学生所选择的宿舍楼编号。

输出格式

输出的第一行且仅有一行，包含所求的最小可能总噪音值。

子任务

• 在价值 40 分的测试数据中，满足 $M = 1$。
• 在价值 60 分的测试数据中，满足 $N \le 1\,000$。
• 在价值 80 分的测试数据中，满足 $N \le 50\,000$。

样例

输入 1

5 1 2
1
1
1
1
1

输出 1

7

输入 2

11 2 3
1
2
1
2
1
2
1
2
1
2
1

输出 2

18

说明

样例 1 说明：在第一天和第三天结束后清空宿舍楼，因此每天的噪音值分别为 $1, 1, 2, 1, 2$。如果我们不清空宿舍楼，噪音值将分别为 $1, 2, 3, 4, 5$。

样例 2 说明：例如，在第四天和第八天结束后清空 1 号楼，在第六天结束后清空 2 号楼。每天的噪音值分别为 $1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2$。