AT_codequeen2024_final_h Good bye, AtCoder Land.

AtCoder Land 有 $N$ 个游乐设施。 第 $i$ 个游乐设施有如下两种乘坐方式： - 正常乘坐。 - $A_i$ 分钟后乘坐结束。 - 使用快速通行证乘坐。 - $B_i$ 分钟后乘坐结束，此时会消耗 $1$ 张快速通行证。 你有 $K$ 张快速通行证。 假设同一个游乐设施不能重复乘坐，最多可以在 $T$ 分钟内乘坐多少个游乐设施？ 注意，不需要考虑换乘游乐设施所需的时间，且最后乘坐的游乐设施必须在 $T$ 分钟内结束。

输入按以下格式从标准输入读入。 > $N$ $K$ $T$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

请输出可以乘坐的最多游乐设施数量，作为一个整数。

### 样例解释 1 在此输入中，AtCoder Land 有 $5$ 个游乐设施，你有 $2$ 张快速通行证。 - 首先，对第 $5$ 个游乐设施使用快速通行证。 - 此时，$5$ 分钟后乘坐结束，快速通行证剩余 $1$ 张，共耗时 $5$ 分钟。 - 接着，正常乘坐第 $3$ 个游乐设施。 - 此时，$3$ 分钟后乘坐结束，共耗时 $8$ 分钟。 - 然后，对第 $1$ 个游乐设施使用快速通行证。 - 此时，$4$ 分钟后乘坐结束，快速通行证剩余 $0$ 张，共耗时 $12$ 分钟。 - 最后，正常乘坐第 $4$ 个游乐设施。 - 此时，$8$ 分钟后乘坐结束，共耗时 $20$ 分钟。 按照上述方式，可以乘坐 $4$ 个游乐设施，并且这已经是最大数量。 ### 样例解释 2 也有可能在 $T$ 分钟内一个游乐设施都无法乘坐。 ### 样例解释 3 有时也可以在 $T$ 分钟内乘坐完全部游乐设施。 ### 数据范围 - 输入均为整数 - $1 \le K \le N \le 2 \times 10^5$ - $1 \le T \le 10^{18}$ - $1 \le B_i \le A_i \le 10^{12}$ 由 ChatGPT 5 翻译