题目描述

Farmer John 决定让他的奶牛表演杂技！首先，FJ 为他的奶牛称重，发现她们有 $N$（$1\le N\le 2\times 10^5$）个不同的体重。具体来说，对于全部的 $i\in [1,N]$，有 $a_i$ 只奶牛的体重为 $w_i$ 单位（$1\le a_i\le 10^9, 1\le w_i\le 10^9$）。

他最出名的节目需要奶牛叠成平衡的奶牛塔。一座奶牛塔是一些奶牛，每只奶牛站在下一只奶牛身上。一座奶牛塔是平衡的，当且仅当每一只被踩着的奶牛，都比直接踩在它身上的那只奶牛重至少 $K$（$1\le K\le 10^9$）单位。每只奶牛都可以成为奶牛塔的一部分。

如果 FJ 想要创造最多 $M$（$1 \le M \le 10^9$）座奶牛塔，最多有多少只奶牛可以成为奶牛塔的一部分？

输入格式

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

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

输出格式

输出当 FJ 采用最佳方案时，奶牛塔中奶牛的最大数目。

3 5 2
9 4
7 6
5 5

14

3 5 3
5 5
7 6
9 4

9

提示

样例解释 1

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

样例解释 2

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

测试点性质

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