题目描述

题目译自 Open Olympiad in Informatics 2024 Day1 T3 「Больше подарков хороших и разных / More Gifts」。

组织者准备了 $k$ 个相同的礼物盒，每个盒子内有 $n$ 个礼物，从上到下类型依次为 $a_1, a_2, \ldots, a_n$。分发规则如下：

1. 按盒子顺序分发，先从第一个盒子自上而下分发，空了再用第二个，直至第 $k$ 个盒子；
2. 礼物按参赛者顺序分发，先给第一名，再给第二名，以此类推；
3. 每名参赛者获得的礼物类型不超过 $t$ 种（可重复获得同类型）。

需确定最少需要邀请的参赛者数量，以分发所有礼物并满足上述约束。

输入格式

1. 第一行：三个整数 $n, k, t$（$1 \leq n \leq 300000$，$1 \leq k, t \leq 10^9$），分别表示每个盒子的礼物数、盒子数、每名参赛者最多可获得的礼物类型数；
2. 第二行：$n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示单个盒子内从上到下的礼物类型。

输出格式

输出一个整数，即最少需要的参赛者数量。

样例

样例 1

输入

2 4 1
1 2

输出

8

在第一个样例中，每个盒子包含的礼物类型（从上到下）如下，颜色不同表示盒子中的不同位置：

共有 4 个盒子，礼物将按以下顺序分发：

由于 t = 1，每名参赛者只能获得一种类型的礼物：

样例 2

输入

4 3 1
1 1 2 1

输出

7

在第二个样例中，礼物分发顺序和最终的礼物套装如下：

样例 3

输入

7 2 3
1 2 3 4 5 6 7

输出

5

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

一种可能的最优分发方案如下：