레이팅 미적용설명
농부 존(Farmer John)에게는 새 소가 필요하다! 판매 중인 소는 N마리 (1 <= N <= 50,000)이고, FJ는 예산 M 단위 (1 <= M <= 10^14)를 초과하여 쓸 수 없다. 소 i의 가격은 P_i (1 <= P_i <= 10^9)이지만, FJ에게는 K장 (1 <= K <= N)의 쿠폰이 있어서 소 i에 쿠폰을 사용하면 가격이 C_i (1 <= C_i <= P_i)가 된다. 물론 FJ는 소 한 마리당 쿠폰을 한 장만 쓸 수 있다.
FJ가 살 수 있는 소의 최대 수는 얼마인가?
제약
입력 형식
첫째 줄: 공백으로 구분된 세 정수 N, K, M.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 두 정수 P_i와 C_i가 주어진다.
출력 형식
FJ가 살 수 있는 소의 최대 수를 나타내는 정수 하나.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
coupons.in · 출력을 쓸 파일 coupons.out예제 1
입력
4 1 7
3 2
2 2
8 1
4 3출력
3설명
Input details: FJ has 4 cows, 1 coupon, and a budget of 7.
Output details: FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > February > Gold
태그