Farmer John нужны новые коровы! Продаётся $N$ коров, $1 \le N \le 50,000$, бюджет FJ — не более $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