문제
농부 존은 새 소들이 필요하다! 현재 N(1 <= N <= 50,000)마리의 소가 판매 중이고 농부 존은 M(1 <= M <= 1014)원 이상의 금액을 사용 할 수 없다.
i번째 소를 구입하려면 Pi(1 <= P_i <= 109)의 비용이 들지만, 농부 존에게는 K(1 <= K <= N)개의 쿠폰이 있다.
어떠한 소를 구입 할 때 쿠폰을 사용하면 소의 가격은 Pi원 대신 Ci(1 <= C_i <= P_i)원이 된다.
하지만 당연하게도 농부 존은 소 한마리당 한장의 쿠폰을 사용할수있다.
농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.
입력
첫 번째 줄: 공백을 기준으로 N, K, M
두 번째부터 N+1 줄까지: i+1번째 줄에 두 정수 Pi와 Ci
출력
첫 번째 줄: 농부 존이 최대로 살 수 있는 소 마릿수
예제1
입력
4 1 7
3 2
2 2
8 1
4 3
출력
3
힌트
출처
USACO 2012 February Contest, Gold