RiseOJ – 선물

설명

농부 존(Farmer John)은 총 B (1 <= B <= 1,000,000,000) 단위의 예산으로 N마리 (1 <= N <= 1000)의 소들에게 선물을 주고 싶어 한다.

소 i는 가격이 P(i) 단위이고 배송비가 S(i) 단위인 선물을 원한다 (따라서 FJ가 이 선물을 주문하는 데 드는 총비용은 P(i)+S(i)이다). FJ에게는 원하는 선물 하나를 정가의 절반에 주문할 수 있는 특별 쿠폰이 있다. FJ가 소 i에게 쿠폰을 사용하면, 그 소의 선물에는 P(i)/2+S(i)만 지불하면 된다. 편리하게도 P(i)는 모두 짝수이다.

FJ가 예산 안에서 선물을 줄 수 있는 소의 최대 수를 구하는 것을 도와주자.

제약

입력 형식

첫째 줄: 공백으로 구분된 두 정수 N과 B.

둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 공백으로 구분된 두 정수 P(i)와 S(i)가 주어진다. (0 <= P(i),S(i) <= 1,000,000,000, P(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:

입력을 읽을 파일 gifts.in · 출력을 쓸 파일 gifts.out

예제 1

입력

출력

설명

Input details: There are 5 cows, and FJ has a budget of 24.

Output details: FJ can purchase gifts for cows 1 through 4, if he uses the coupon for cow 3. His total cost is (4+2)+(2+0)+(4+1)+(6+3) = 22.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2011-2012 > January > Bronze

올림피아드 > USACO > 2011-2012 > January > Bronze

태그

JudgeUSACO

선물

평가 및 의견

풀이 제출