페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3762

쿠폰 1s 128MB

문제

농부 존은 새 소들이 필요하다! 현재 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)​개​의 쿠폰이 있다.

어떠한 소를 구입 할 때 쿠폰을 사용하면 소의 가격은 P_i원 대신 C_i​(1 \le C_i \le P_i)​원이 된다.

하지만 당연하게도 농부 존은 소 한마리당 한장의 쿠폰을 사용할수있다.

농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.​


입력

첫 번째 줄: 공백을 기준으로 N, K, M

두 번째부터 N+1 줄까지: i+1번째 줄에 두 정수 P_i와 C_i​


출력

첫 번째 줄: 농부 존이 최대로 살 수 있는 소 마릿수


예제 

4 1 7

3 2

2 2

8 1

4 3
3

4마리의 소가 있는데, 농부 존은 1개의 쿠폰과 자산 7원을 가지고 있다.

농부 존은​ 3번째 소에 쿠폰 하나를 쓰고 1,2,3번 소를 산다. (1 + 2 + 3 = 6원)​​



출처

USACO 2012 February Contest, Gold
로그인해야 코드를 작성할 수 있어요.