该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$Farmer$ $John$决定让他的奶牛表演杂技！首先，$Farmer$ $John$为他的奶牛称重，发现她们有$N$（$1\leq N\leq 2\times 10^{5}$）个不同的体重。具体来说，对于全部的$i\in [1,N]$，有$a_{i}$只奶牛的体重为$w_{i}$单位（$1\leq a_{i}\leq 10^{9}$，$1\leq w_{i}\leq 10^{9}$）。他最受欢迎的绝活是让奶牛们组成平衡塔。一个塔是一系列奶牛，其中每头奶牛都叠在上一头的上面。如果每头奶牛和它上面的奶牛的重量差至少为$K$（$1\leq K\leq 10^{9}$），那么这个塔是平衡的。任何奶牛最多只能是一个平衡塔的一部分。

如果$Farmer$ $John$想要创造最多$M$（$1\leq M\leq 10^{9}$）个平衡塔，那么最多有多少头奶牛可以成为某个塔的一部分？

输入格式

第一行包含三个空格分隔的整数$N$，$M$和$K$。

接下来$N$行，每行包含两个空格分隔的整数$w_{i}$和$a_{i}$。保证所有的$w_{i}$是不同的。

输出格式

如果$Farmer$ $John$帮助奶牛们最优地组成塔，输出平衡塔中最多的奶牛数。

数据范围

• 数据点$3$-$5$满足$M\leq 5000$且奶牛的总数不超过$5000$。
• 数据点$6$-$11$满足奶牛的总数不超过$2\cdot 10^{5}$。
• 数据点$12$-$17$没有额外限制。

样例数据

3 5 2
9 4
7 6
5 5

14

说明

$Farmer$ $John$可以用体重为$5$,$7$,$9$的奶牛创造四座平衡塔，再用体重为$5$,$7$的奶牛创造另一座。

3 5 3
5 5
7 6
9 4

9

说明

$Farmer$ $John$可以用体重为$5$,$9$的奶牛创造四座平衡塔，再用体重为$7$的一只奶牛创造另一座。或者，他可以用体重为$5$,$9$的奶牛创造四座平衡塔，再用体重为$5$的一只奶牛创造另一座。