题目描述

$\red{FJ}$准备买一些新奶牛，市场上有$\red{N}$头奶牛$\red{(1<=N<=50000)，}$第$\red{i}$头奶牛价格为$\red{P_i(1<=P_i<=10^9)}$。$\red{FJ}$有$\red{K}$张优惠券，使用优惠券购买第$\red{i}$头奶牛时 价格会降为$\red{C_i(1<=C_i<=P_i)，}$每头奶牛只能使用一次优惠券。$\red{FJ}$想知道花不超过$\red{M(1<=M<=10^{14})}$的钱最多可以买多少奶牛？

输入格式

第 $\red{1 }$行：三个以空格分隔的整数：$\red{N}$、$\red{K }$和 $\red{M}$。

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行包含两个整数：$\red{P_i }$和 $\red{C_i}$。

输出格式

第 $\red{1 }$行：单个整数，$\red{FJ }$可以承受的最大奶牛数。

样例

输入样例

4 1 7 
3 2 
2 2 
8 1 
4 3

输出样例

3

提示

$\red{FJ }$有 $\red{4 }$头奶牛，$\red{1 }$张优惠券，预算为 $\red{7}$。

$\red{FJ }$使用奶牛 $\red{3 }$的优惠券购买奶牛 $\red{1}$、$\red{2 }$和 $\red{3，}$总成本为 $\red{3 + 2 + 1 = 6}$。