시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 97 25 19 22.619%

문제

농부 존은 새 소들이 필요하다! 그래서 농부 존은 소 시장에 가서 새 소들을 사려고 한다.

농부 존은 돈이 많이 없기 때문에 소들을 최대한 효율적으로 사야 한다. 그래서 농부 존은 M원과 K개의 소 쿠폰을 가지고 소 시장에 나온 N마리의 소들을 최대한 많이 사려고 한다.

소 쿠폰은 소 한 마리당 한 번만 쓸 수 있고, 쓰고 나면 사라진다. i번째 소는 Pi원이고, 쿠폰을 썼을 때는 Ci원이 될 때, 농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.

입력

첫 번째 줄에 소 시장에 나온 소들의 마릿수 N(1 ≤ N ≤ 50,000), 농부 존이 가지고 있는 쿠폰의 개수 K(1 ≤ K ≤ N), 농부 존이 가지고 있는 돈 M(1 ≤ M ≤ 1014)이 주어진다.

다음 줄부터 Pi (1 ≤ Pi ≤ 109), Ci (1 ≤ Ci ≤ Pi)가 주어진다.

출력

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

예제 입력

4 1 7
3 2
2 2
8 1
4 3

예제 출력

3

힌트

농부 존은 1개의 쿠폰과 7원을 가지고 소 시장에 갔다.

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

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO February 2012 Contest > Gold 1번

  • 데이터를 추가한 사람: appa
  • 문제를 번역한 사람: onjo0127