시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 360 92 81 37.327%

문제

시흠이는 군대에 가기 전까지 자신과 놀아준 친구 N(1 ≤ N ≤ 1000)명에게 선물을 주려고 한다. 시흠이는 돈을 B(1 ≤ B ≤ 1,000,000,000)원 가지고 있다.

i번째 친구가 받고 싶어하는 선물의 가격은 P(i)원이고, 배송비는 S(i)원이다. 즉, 시흠이가 i번째 친구에게 선물을 보내려면 돈이 P(i)+S(i)원 필요하다.

시흠이는 물건 가격을 절반으로 할인받을 수 있는 쿠폰을 하나 가지고 있다. 이 쿠폰을 i번째 친구에게 사용한다면, P(i)/2+S(i)원만 있으면 선물을 보낼 수 있다.

시흠이가 선물을 최대 몇 명에게 보낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 B가 주어진다. 둘째 줄부터 N개 줄에는 P(i)와 S(i)가 주어진다. (0 ≤ P(i), S(i) ≤ 1,000,000,000, P(i)는 짝수)

출력

첫째 줄에 시흠이가 선물을 최대 몇 명에게 보낼 수 있는지 출력한다.

예제 입력 1

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

예제 출력 1

4

힌트

1, 2, 4번 친구의 선물을 구매하고, 3번 친구의 선물을 쿠폰을 써서 구매하면 된다. (4+2)+(2+0)+(4+1)+(6+3) = 22 이기 때문에, B원으로 모두 구매하고 배송보낼 수 있다. 또, 1번이나 4번 친구에게 쿠폰을 써도 된다.

W3sicHJvYmxlbV9pZCI6IjU5MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMjBcdWJiM2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJkY1x1ZDc2MFx1Yzc3NFx1YjI5NCBcdWFkNzBcdWIzMDBcdWM1ZDAgXHVhYzAwXHVhZTMwIFx1YzgwNFx1YWU0Y1x1YzljMCBcdWM3OTBcdWMyZTBcdWFjZmMgXHViMTgwXHVjNTQ0XHVjOTAwIFx1Y2U1Y1x1YWQ2YyBOKDEgJmxlOyBOICZsZTsgMTAwMClcdWJhODVcdWM1ZDBcdWFjOGMgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzJkY1x1ZDc2MFx1Yzc3NFx1YjI5NCBcdWIzYzhcdWM3NDQgQigxICZsZTsgQiAmbGU7IDEsMDAwLDAwMCwwMDApXHVjNmQwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHVjZTVjXHVhZDZjXHVhYzAwIFx1YmMxYlx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBQKGkpXHVjNmQwXHVjNzc0XHVhY2UwLCBcdWJjMzBcdWMxYTFcdWJlNDRcdWIyOTQgUyhpKVx1YzZkMFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWMyZGNcdWQ3NjBcdWM3NzRcdWFjMDAgaVx1YmM4OFx1YzlmOCBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YmNmNFx1YjBiNFx1YjgyNFx1YmE3NCBcdWIzYzhcdWM3NzQgUChpKStTKGkpXHVjNmQwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVkNzYwXHVjNzc0XHViMjk0IFx1YmIzY1x1YWM3NCBcdWFjMDBcdWFjYTlcdWM3NDQgXHVjODA4XHViYzE4XHVjNzNjXHViODVjIFx1ZDU2MFx1Yzc3OFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2ZlMFx1ZDNmMFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1Y2ZlMFx1ZDNmMFx1Yzc0NCBpXHViYzg4XHVjOWY4IFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTRcdWJhNzQsIFAoaSlcLzIrUyhpKVx1YzZkMFx1YjljYyBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWQ3NjBcdWM3NzRcdWFjMDAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViYTg1XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFAoaSlcdWM2NDAgUyhpKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgUChpKSwgUyhpKSAmbGU7IDEsMDAwLDAwMCwwMDAsIFAoaSlcdWIyOTQgXHVjOWRkXHVjMjE4KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHVkNzYwXHVjNzc0XHVhYzAwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmE4NVx1YzVkMFx1YWM4YyBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjEsIDIsIDRcdWJjODggXHVjZTVjXHVhZDZjXHVjNzU4IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWFjZTAsIDNcdWJjODggXHVjZTVjXHVhZDZjXHVjNzU4IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNmZTBcdWQzZjBcdWM3NDQgXHVjMzY4XHVjMTFjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuICg0KzIpKygyKzApKyg0KzEpKyg2KzMpID0gMjIgXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgQlx1YzZkMFx1YzczY1x1Yjg1YyBcdWJhYThcdWI0NTAgXHVhZDZjXHViOWU0XHVkNTU4XHVhY2UwIFx1YmMzMFx1YzFhMVx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIDFcdWJjODhcdWM3NzRcdWIwOTggNFx1YmM4OCBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHVjZmUwXHVkM2YwXHVjNzQ0IFx1YzM2OFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1OTExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2lmdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIHdhbnRzIHRvIGdpdmUgZ2lmdHMgdG8gaGlzIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAwKSBjb3dzLCB1c2luZyBoaXMgdG90YWwgYnVkZ2V0IG9mIEIgKDEgJmx0Oz0gQiAmbHQ7PSAxLDAwMCwwMDAsMDAwKSB1bml0cyBvZiBtb25leS48XC9wPlxyXG5cclxuPHA+Q293IGkgcmVxdWVzdHMgYSBnaWZ0IHdpdGggYSBwcmljZSBvZiBQKGkpIHVuaXRzLCBhbmQgYSBzaGlwcGluZyBjb3N0IG9mIFMoaSkgdW5pdHMgKHNvIHRoZSB0b3RhbCBjb3N0IHdvdWxkIGJlIFAoaSkrUyhpKSBmb3IgRkogdG8gb3JkZXIgdGhpcyBnaWZ0KS4gJm5ic3A7RkogaGFzIGEgc3BlY2lhbCBjb3Vwb24gdGhhdCBoZSBjYW4gdXNlIHRvIG9yZGVyIG9uZSBnaWZ0IG9mIGhpcyBjaG9vc2luZyBhdCBvbmx5IGhhbGYgaXRzIG5vcm1hbCBwcmljZS4gJm5ic3A7SWYgRkogdXNlcyB0aGUgY291cG9uIGZvciBjb3cgaSwgaGUgdGhlcmVmb3JlIHdvdWxkIG9ubHkgbmVlZCB0byBwYXkgUChpKVwvMitTKGkpIGZvciB0aGF0IGNvdyYjMzk7cyBnaWZ0LiBDb252ZW5pZW50bHksIHRoZSBQKGkpJiMzOTtzIGFyZSBhbGwgZXZlbiBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5QbGVhc2UgaGVscCBGSiBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNvd3MgdG8gd2hvbSBoZSBjYW4gYWZmb3JkIHRvIGdpdmUgZ2lmdHMuICZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIE4gYW5kIEIuPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uMStOOiBMaW5lIGkrMSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBQKGkpIGFuZCBTKGkpLiAmbmJzcDsoMCAmbHQ7PSBQKGkpLFMoaSkgJmx0Oz0gMSwwMDAsMDAwLDAwMCwgd2l0aCBQKGkpIGV2ZW4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBtYXhpbXVtIG51bWJlciBvZiBjb3dzIGZvciB3aG9tIEZKIGNhbiBwdXJjaGFzZSBnaWZ0cy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZXJlIGFyZSA1IGNvd3MsIGFuZCBGSiBoYXMgYSBidWRnZXQgb2YgMjQuICZuYnNwO0NvdyAxIGRlc2lyZXMgYSBnaWZ0IHdpdGggcHJpY2UgNCBhbmQgc2hpcHBpbmcgY29zdCAyLCBldGMuPFwvcD5cclxuXHJcbjxwPkZKIGNhbiBwdXJjaGFzZSBnaWZ0cyBmb3IgY293cyAxIHRocm91Z2ggNCwgaWYgaGUgdXNlcyB0aGUgY291cG9uIGZvciBjb3cgMy4gJm5ic3A7SGlzIHRvdGFsIGNvc3QgaXMgKDQrMikrKDIrMCkrKDQrMSkrKDYrMykgPSAyMi4gJm5ic3A7Tm90ZSB0aGF0IEZKIGNvdWxkIGhhdmUgdXNlZCB0aGUgY291cG9uIGluc3RlYWQgb24gY293IDEgb3IgNCBhbmQgc3RpbGwgbWV0IGhpcyBidWRnZXQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO January 2012 Contest > Bronze 1번