题目描述

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

输入格式

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

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

输出格式

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

样例

输入样例

4 1 7 
3 2 
2 2 
8 1 
4 3

输出样例

3

提示

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

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