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

附加文件

问题描述

商场里共 N 件商品，对于第 i 件商品，价格为 Ai，会员价为 Bi，保证会员价 Bi 不会比原价 Ai 高。

会员最多只能享受 K 件商品的会员价。至于哪些件商品享受会员价，则由顾客来决定。

小明是会员，他有 M 元钱。

问：他最多可以买多少件商品？

输入格式

第一行: 三个整数 N, K, M

接下来 N 行: 每行 2 个整数 Ai, Bi

输出格式：

一个整数, 表示小明最多可买到的商品件数

输入样例

4 1 7 
2 2 
3 2 
6 1 
5 3

输出样例

3

数据范围

20% 的数据：1 ≤ N ≤ 5

40% 的数据：1 ≤ N ≤ 5000

100% 的数据：1 ≤ N ≤ 50000， 0 ≤ K ≤ N， 1 ≤ Bi ≤ Ai ≤ 10^9， 1 ≤ M ≤ 10^14