闭合信息学奥林匹克（Closed Olympiad in Informatics）的组织者决定为参赛者准备礼物。他们一共准备了 $k$ 个相同的礼物盒，每个盒子里面有一叠共 $n$ 个礼物。在每一叠礼物的最上方是类型为 $a_1$ 的礼物，其下方是类型为 $a_2$ 的礼物，依此类推，最下方是类型为 $a_n$ 的礼物。

礼物的发放规则如下：首先，从第一叠礼物中按从上到下的顺序依次发放。当第一叠礼物发放完毕后，再从第二叠礼物中按从上到下的顺序依次发放，依此类推，最后发放第 $k$ 叠礼物。

每位参赛者可以一次性获得多个礼物。因此，最开始礼物会发放给第一位参赛者，接着是第二位，依此类推。已知如果一位参赛者收到了超过 $t$ 种不同类型的礼物，他会过于兴奋导致奥林匹克竞赛发挥失常。为了让参赛者们能取得好成绩，组织者决定每位参赛者最多只能收到 $t$ 种不同类型的礼物（注意，一位参赛者可以收到多个相同类型的礼物）。

闭合信息学奥林匹克的组织者决定让这次竞赛显得更加独特，因此希望邀请尽可能少的参赛者。请帮助组织者求出最少需要邀请多少位参赛者，才能将所有的礼物都发放完毕，且每位参赛者收到的礼物中不同类型的数量不超过 $t$。

输入格式

输入的第一行包含三个整数 $n$、$k$ 和 $t$（$1 \le n \le 300\,000$，$1 \le k, t \le 10^9$）—— 分别表示一叠礼物的数量、礼物叠的数量，以及每位参赛者最多可以收到的不同类型礼物的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示一叠礼物中从上到下的礼物类型。

输出格式

输出一个整数 —— 表示最少需要的参赛者人数，使得所有礼物都能发放给他们，且每位参赛者收到的不同类型礼物的数量不超过 $t$。

样例

输入样例 1

2 4 1
1 2

输出样例 1

8

输入样例 2

4 3 1
1 1 2 1

输出样例 2

7

输入样例 3

7 2 3
1 2 3 4 5 6 7

输出样例 3

5

说明

在第一个样例中，一叠礼物包含以下类型的礼物（按从上到下的顺序）。不同的颜色表示在礼物叠中的不同位置。

一共有 4 叠礼物，因此礼物将按以下顺序发放：

由于 $t = 1$，在这种情况下，每位参赛者只能收到一种类型的礼物：

在第二个样例中，礼物的发放顺序以及最终的礼物分组如下：

在第三个样例中，礼物的发放顺序如下：

在这种情况下，一种可能的将礼物分配给参赛者的最优方案如下：

子任务

本题的测试点由六个子任务组成。只有当通过该子任务的所有测试点以及所有依赖的子任务的测试点时，才能获得该子任务的分数。请注意，某些子任务并不要求通过样例测试。