시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 471 107 91 32.155%

문제

시흠이는 군대에 가기 전까지 자신과 놀아준 친구 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)

출력

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

예제 입력 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+XHVjMmRjXHVkNzYwXHVjNzc0XHViMjk0IFx1YmIzY1x1YWM3NCBcdWFjMDBcdWFjYTlcdWM3NDQgXHVjODA4XHViYzE4XHVjNzNjXHViODVjIFx1ZDU2MFx1Yzc3OFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2ZlMFx1ZDNmMFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1Y2ZlMFx1ZDNmMFx1Yzc0NCBpXHViYzg4XHVjOWY4IFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTRcdWJhNzQsICZsZmxvb3I7UChpKVwvMiZyZmxvb3I7K1MoaSlcdWM2ZDBcdWI5Y2MgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVkNzYwXHVjNzc0XHVhYzAwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmE4NVx1YzVkMFx1YWM4YyBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBQKGkpXHVjNjQwIFMoaSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IFAoaSksIFMoaSkgJmxlOyAxLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHVkNzYwXHVjNzc0XHVhYzAwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmE4NVx1YzVkMFx1YWM4YyBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjEsIDIsIDRcdWJjODggXHVjZTVjXHVhZDZjXHVjNzU4IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWFjZTAsIDNcdWJjODggXHVjZTVjXHVhZDZjXHVjNzU4IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNmZTBcdWQzZjBcdWM3NDQgXHVjMzY4XHVjMTFjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuICg0KzIpKygyKzApKyg0KzEpKyg2KzMpID0gMjIgXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgQlx1YzZkMFx1YzczY1x1Yjg1YyBcdWJhYThcdWI0NTAgXHVhZDZjXHViOWU0XHVkNTU4XHVhY2UwIFx1YmMzMFx1YzFhMVx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIDFcdWJjODhcdWM3NzRcdWIwOTggNFx1YmM4OCBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHVjZmUwXHVkM2YwXHVjNzQ0IFx1YzM2OFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1OTExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2lmdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIHdhbnRzIHRvIGdpdmUgZ2lmdHMgdG8gaGlzIE4gKDEgJmxlOyZuYnNwO04gJmxlOyZuYnNwOzEwMDApIGNvd3MsIHVzaW5nIGhpcyB0b3RhbCBidWRnZXQgb2YgQiAoMSAmbGU7Jm5ic3A7QiAmbGU7Jm5ic3A7MSwwMDAsMDAwLDAwMCkgdW5pdHMgb2YgbW9uZXkuPFwvcD5cclxuXHJcbjxwPkNvdyBpIHJlcXVlc3RzIGEgZ2lmdCB3aXRoIGEgcHJpY2Ugb2YgUChpKSB1bml0cywgYW5kIGEgc2hpcHBpbmcgY29zdCBvZiBTKGkpIHVuaXRzIChzbyB0aGUgdG90YWwgY29zdCB3b3VsZCBiZSBQKGkpK1MoaSkgZm9yIEZKIHRvIG9yZGVyIHRoaXMgZ2lmdCkuICZuYnNwO0ZKIGhhcyBhIHNwZWNpYWwgY291cG9uIHRoYXQgaGUgY2FuIHVzZSB0byBvcmRlciBvbmUgZ2lmdCBvZiBoaXMgY2hvb3NpbmcgYXQgb25seSBoYWxmIGl0cyBub3JtYWwgcHJpY2UuICZuYnNwO0lmIEZKIHVzZXMgdGhlIGNvdXBvbiBmb3IgY293IGksIGhlIHRoZXJlZm9yZSB3b3VsZCBvbmx5IG5lZWQgdG8gcGF5ICZsZmxvb3I7UChpKVwvMiZyZmxvb3I7K1MoaSkgZm9yIHRoYXQgY293JiMzOTtzIGdpZnQuIENvbnZlbmllbnRseSwgdGhlIFAoaSkmIzM5O3MgYXJlIGFsbCBldmVuIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPlBsZWFzZSBoZWxwIEZKIGRldGVybWluZSB0aGUgbWF4aW11bSBudW1iZXIgb2YgY293cyB0byB3aG9tIGhlIGNhbiBhZmZvcmQgdG8gZ2l2ZSBnaWZ0cy4gJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgTiBhbmQgQi48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uMStOOiBMaW5lIGkrMSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBQKGkpIGFuZCBTKGkpLiAmbmJzcDsoMCAmbGU7IFAoaSksIFMoaSkgJmxlOyAxLDAwMCwwMDAsMDAwKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBtYXhpbXVtIG51bWJlciBvZiBjb3dzIGZvciB3aG9tIEZKIGNhbiBwdXJjaGFzZSBnaWZ0cy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5UaGVyZSBhcmUgNSBjb3dzLCBhbmQgRkogaGFzIGEgYnVkZ2V0IG9mIDI0LiAmbmJzcDtDb3cgMSBkZXNpcmVzIGEgZ2lmdCB3aXRoIHByaWNlIDQgYW5kIHNoaXBwaW5nIGNvc3QgMiwgZXRjLjxcL3A+XHJcblxyXG48cD5GSiBjYW4gcHVyY2hhc2UgZ2lmdHMgZm9yIGNvd3MgMSB0aHJvdWdoIDQsIGlmIGhlIHVzZXMgdGhlIGNvdXBvbiBmb3IgY293IDMuICZuYnNwO0hpcyB0b3RhbCBjb3N0IGlzICg0KzIpKygyKzApKyg0KzEpKyg2KzMpID0gMjIuICZuYnNwO05vdGUgdGhhdCBGSiBjb3VsZCBoYXZlIHVzZWQgdGhlIGNvdXBvbiBpbnN0ZWFkIG9uIGNvdyAxIG9yIDQgYW5kIHN0aWxsIG1ldCBoaXMgYnVkZ2V0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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