Farmer John は新しい牛が必要です！$N$ 頭が売られ、$1 \le N \le 50,000$ です。予算は $M$、$1 \le M \le 10^{14}$ で超えてはいけません。牛 $i$ は $P_{i}$、$1 \le P_{i} \le 10^9$ です。$K$ 枚のクーポン（$1 \le K \le N$）があり、牛 $i$ に使うと $C_{i}$（$1 \le C_{i} \le P_{i}$）になります。一頭に一枚までです。

FJ は最大何頭買えますか？

入力

• $1$ 行目：空白区切りの整数 $N$、$K$、$M$。

• $2..N+1$ 行目：$i+1$ 行目に整数 $P_{i}$、$C_{i}$。

出力

• $1$ 行目：買える牛の最大数を表す整数。

入出力例

入力 1

4 1 7
3 2
2 2
8 1
4 3

出力 1

3

注記

FJ には $4$ 頭の牛、$1$ 枚のクーポン、予算 $7$ があります。

牛 $3$ に使い、$1$、$2$、$3$ を買うと総費用は $3 + 2 + 1 = 6$ です。

問題作成者：Neal Wu と Mark Gordon、2012