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}$)로 바뀐다. 젖소당 쿠폰 한 장만 쓴다.

최대 몇 마리 살 수 있는가?

입력

• $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