题目描述

给定一个长度为 $n$ 的正整数序列 $A = (A_1,A_2,\dots,A_n)$，以及非负整数 $k$ 和正整数 $d$。

你可以构造一个正整数多重集合 $B$，满足 $|B| \le k$。$B$ 中元素没有数值上界，也允许出现重复值。

从 $A$ 和 $B$ 的所有元素中选出若干个互不相同的整数，组成集合 $T$。将 $T$ 严格递增排列为 $t_1 < t_2 < \dots < t_m$，要求对每个 $1 \le i < m$ 都有

求 $m = |T|$ 的最大值。由于 $T$ 中的整数互不相同，$A$ 或 $B$ 中相同的数值最多对答案贡献一次。

输入格式

第一行包含三个整数 $n,k,d$。

第二行包含 $n$ 个正整数 $A_1,A_2,\dots,A_n$。

输出格式

输出一行一个整数，表示 $|T|$ 的最大值。

样例

5 1 2
1 4 8 9 13

4

8 2 3
10 15 2 4 16 11 5 20

9

样例解释

对于样例1： 可以选取 $A$ 中的 $\{4,8,9\}$，令 $B=\{6\}$，得到 $T=\{4,6,8,9\}$。

对于样例2： 例如选取 $A$ 中的 $\{2,4,5,10,11,15,16\}$，令 $B=\{8,14\}$。

数据规模与约定

本题采用捆绑测试。对于所有数据： $1 \le n \le 10^5,\ 0 \le k \le 10^9,\ 1 \le d,A_i \le 10^9$。

原题链接

原题链接