Informatica Online Judge

  선물 [0499 / 01F3]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 51   Total Tried : 60


The Champion of this Problem (C++) : gs14072 - ms / 631byte
My Best Submission (C++) : N/A

[]

Background

농부 존은 젖소들의 탈출에 충격을 받아서 앞으로 젖소들을 보다 잘 보살피기로 했다.

그래서 이번에 특별히 그의 예산이 허락하는 범위에서 선물을 준비했다.

농부 존은 그의 N(1<=N<=1,000)마리의 젖소들에게 그의 예산 B(1<=B<=1,000,000,000)원으로 선물을 사 주려고 한다.

i번째 소에게 드는 비용은 선물의 값 P(i)와 이 선물을 배송하는데 드는 비용 S(i)가 든다. 즉 i번째 소에게 들어가는 총 비용은 P(i)+S(i)이다.

농부존은 특별한 쿠폰을 가지고 있다. 이 쿠폰은 딱 하나의 선물에 적용할 수 있으며, 적용할 시에 선물의 가격이 반으로 할인된다. 즉 쿠폰을 사용한다면 드는 비용이 P(i)/2+S(i)가 된다.

참고로 모든 선물의 비용은 짝수이다.

이 쿠폰을 한 장 사용할 수 있다고 할 때, 가장 많은 소들에게 선물을 주고자 한다. 각 소들에게 드는 비용이 주어질 때, 선물을 줄 수 있는 가장 많은 소를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 소의 수 N과 예산 B가 공백으로 구분되어 입력된다.
두 번째 줄부터 N줄에 걸쳐서 선물의 가격과 배송비가 공백으로 구분되어 입력된다.

Output

쿠폰을 사용하여 선물을 살 수 있는 가장 많은 소의 수를 출력한다.

IO Example

입력
5 24
4 2
2 0
8 1
6 3
12 5

출력
4

* 설명 : 농부 존은 소 1~4까지 선물을 줄 수 있다. 쿠폰은 3번 소의 선물을 살 때 쓰면 이 값이 최대값이다. 이때 지불한 가격은 (4+2)+(2+0)+(4+1)+(6+3) = 22이다.

USACO 2012 January Contest, Bronze Division

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]