시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 3294 837 529 22.636%

문제

상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다.

두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이 때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다.

상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에, 노트북을 열고 사탕 가게의 시스템을 해킹하기 시작했다. 이 시스템에는 현재 사탕 가게에 있는 사탕의 가격과 칼로리가 모두 등재되어 있다. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다. 또, 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.

사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.

입력

각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다.

다음 n개 줄에는 각 사탕의 칼로리 c와 가격 p가 주어진다. (1 ≤ c ≤ 5,000, 0.01 ≤ p ≤ 100.00) c는 항상 정수, p는 항상 소수점 둘째자리이다.

입력의 마지막 줄에는 '0 0.00'이 주어진다.

출력

각 테스트 케이스에 대해서, 상근이가 돈 m을 가지고 구매할 수 있는 가장 높은 칼로리를 출력한다.

예제 입력 1

2 8.00
700 7.00
199 2.00
3 8.00
700 7.00
299 3.00
499 5.00
0 0.00

예제 출력 1

796
798
W3sicHJvYmxlbV9pZCI6IjQ3ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWQwZDUgXHVhYzAwXHVhYzhjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNjQwIFx1YWM3OFx1YzViNFx1YWMwMFx1YjJlNFx1YWMwMCBcdWMwYWNcdWQwZDUgXHVhYzAwXHVhYzhjXHViOTdjIFx1YzljMFx1YjA5OFx1YWMwMFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YWMxMVx1Yzc5MFx1YWUzMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzBhY1x1ZDBkNVx1Yzc3NCBcdWM1YmNcdWI5YzhcdWIwOTggXHVhYzc0XHVhYzE1XHVjNWQwIFx1YzU0OCBcdWM4OGJcdWM3NDBcdWM5YzAgXHVjMTI0XHViYTg1XHVkNTU4XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjllNFx1YzZiMCBcdWM5ZGNcdWM5OWRcdWM3NzQgXHViMGFjXHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM1ZDBcdWFjOGMgXHViMjA0XHVhYzAwIFx1YjM1NCBcdWFjNzRcdWFjMTVcdWM3NzQgXHVjNTQ4IFx1Yzg4Ylx1YzU0NFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YjBiNFx1YWUzMFx1Yjk3YyBcdWQ1NThcdWM3OTBcdWFjZTAgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMGI0XHVhZTMwXHViOTdjIFx1YWRmOCBcdWM5ODlcdWMyZGMgXHViYzFiXHVjNTQ0XHViNGU0XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWIzYzhcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWMwMFx1YWM4Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWMxMWMgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YzBiMFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhZDZjXHViOWU0XHVkNTVjIFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWNlN2NcdWI4NWNcdWI5YWNcdWFjMDAgXHViMzU0IFx1ZDA3MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMGI0XHVhZTMwXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YWUzMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3YTBcdWMyZGMgXHVkNjU0XHVjN2E1XHVjMmU0XHVjNWQwIFx1YWMxNFx1YjJlNFx1YzYyOFx1YjJlNFx1YWNlMCBcdWQ1NTFcdWFjYzRcdWI5N2MgXHViMzA0IFx1YjRhNFx1YzVkMCwgXHViMTc4XHVkMmI4XHViZDgxXHVjNzQ0IFx1YzVmNFx1YWNlMCBcdWMwYWNcdWQwZDUgXHVhYzAwXHVhYzhjXHVjNzU4IFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWQ1NzRcdWQwYjlcdWQ1NThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LiBcdWM3NzQgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNWQwXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWMwYWNcdWQwZDUgXHVhYzAwXHVhYzhjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzAwXHVhY2E5XHVhY2ZjIFx1Y2U3Y1x1Yjg1Y1x1YjlhY1x1YWMwMCBcdWJhYThcdWI0NTAgXHViNGYxXHVjN2FjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHViOWU0XHVjNmIwIFx1YjljZVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2MgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YWQ2Y1x1YjllNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YzBhY1x1ZDBkNVx1Yzc0MCBcdWNhYmNcdWFjMjQgXHVjMjE4IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3Y1x1YmQ4MFx1YjljYyBcdWFkNmNcdWI5ZTRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVkMGQ1IFx1YWMwMFx1YWM4Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMDBcdWFjYTlcdWFjZmMgXHVjZTdjXHViODVjXHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzViNFx1YjViYlx1YWM4YyBcdWQ1NThcdWJhNzQgXHVjZTdjXHViODVjXHViOWFjXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDZjXHVhYzhjIFx1YjQxOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAwXHVhYzhjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDUgXHVjODg1XHViOTU4XHVjNzU4IFx1YzIxOCBuXHVhY2ZjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjNjOFx1Yzc1OCBcdWM1OTEgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDUsMDAwLCAwLjAxICZsZTsgbSAmbGU7IDEwMC4wMCkgbVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1Y2U3Y1x1Yjg1Y1x1YjlhYyBjXHVjNjQwIFx1YWMwMFx1YWNhOSBwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBjICZsZTsgNSwwMDAsIDAuMDEgJmxlOyBwICZsZTsgMTAwLjAwKSBjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM4MTVcdWMyMTgsIHBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWI0NThcdWM5ZjhcdWM3OTBcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICYjMzk7MCAwLjAwJiMzOTtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjNjOCBtXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWFkNmNcdWI5ZTRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1Y2U3Y1x1Yjg1Y1x1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDc4MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhbmR5IFN0b3JlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHdhbGtpbmcgd2l0aCBhIGZyaWVuZCwgd2hlbiB5b3UgcGFzcyBhIGNhbmR5IHN0b3JlLiBZb3UgbWFrZSBhIGNvbW1lbnQgYWJvdXQgaG93IHVuaGVhbHRoeSB0aGVpciB3YXJlcyBhcmUuIFlvdXIgZnJpZW5kIGlzc3VlcyBhbiBpbnRlcmVzdGluZyBjaGFsbGVuZ2U6IHdobyBjYW4gYmUgdGhlIHVuaGVhbHRoaWVzdD8gQm90aCBvZiB5b3Ugd2lsbCBnbyBpbnRvIHRoZSBzdG9yZSB3aXRoIHRoZSBzYW1lIGFtb3VudCBvZiBtb25leS4gV2hvZXZlciBidXlzIGNhbmR5IHdpdGggdGhlIG1vc3QgdG90YWwgY2Fsb3JpZXMgd2lucyE8XC9wPlxyXG5cclxuPHA+U2luY2UgeW91JiMzOTtyZSBhIHNtYXJ0IGNvbXB1dGVyIHNjaWVudGlzdCwgYW5kIHNpbmNlIHlvdSBoYXZlIGFjY2VzcyB0byB0aGUgY2FuZHkgc3RvcmUmIzM5O3MgaW52ZW50b3J5LCB5b3UgZGVjaWRlIG5vdCB0byB0YWtlIGFueSBjaGFuY2VzLiBZb3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZSBtb3N0IGNhbG9yaWVzIHlvdSBjYW4gYnV5LiBUaGUgaW52ZW50b3J5IHRlbGxzIHlvdSB0aGUgcHJpY2UgYW5kIGNhbG9yaWVzIG9mIGV2ZXJ5IGl0ZW0uIEl0IGFsc28gdGVsbHMgeW91IHRoYXQgdGhlcmUgaXMgc28gbXVjaCBpbiBzdG9jayB0aGF0IHlvdSBjYW4gYnV5IGFzIG11Y2ggb2YgYW55IGtpbmQgb2YgY2FuZHkgYXMgeW91IHdhbnQuIFlvdSBjYW4gb25seSBidXkgd2hvbGUgcGllY2VzIG9mIGNhbmR5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBtdWx0aXBsZSB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZWdpbiB3aXRoIGEgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMSZsZTtuJmxlOzUsMDAwKSwgYW5kIGFuIGFtb3VudCBvZiBtb25leSBtICgkMC4wMSZsZTttJmxlOyQxMDAuMDApLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgdHlwZXMgb2YgY2FuZHkgZm9yIHNhbGUsIGFuZCBtIGlzIHRoZSBhbW91bnQgb2YgbW9uZXkgeW91IGhhdmUgdG8gc3BlbmQuIFRoZSBtb25ldGFyeSBhbW91bnQgbSB3aWxsIGJlIGV4cHJlc3NlZCBpbiBkb2xsYXJzIHdpdGggZXhhY3RseSB0d28gZGVjaW1hbCBwbGFjZXMsIGFuZCB3aXRoIG5vIGxlYWRpbmcgemVyb3MgdW5sZXNzIHRoZSBhbW91bnQgaXMgbGVzcyB0aGFuIG9uZSBkb2xsYXIuIFRoZXJlIHdpbGwgYmUgbm8gZG9sbGFyIHNpZ24uIEVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyB3aWxsIGhhdmUgYW4gaW50ZWdlciBjICgxJmxlO2MmbGU7NSwwMDApIGFuZCBhbiBhbW91bnQgb2YgbW9uZXkgcCAoJDAuMDEmbGU7cCZsZTskMTAwLjAwKSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCB3aGVyZSBjIGlzIHRoZSBudW1iZXIgb2YgY2Fsb3JpZXMgaW4gYSBzaW5nbGUgcGllY2Ugb2YgY2FuZHksIGFuZCBwIGlzIHRoZSBwcmljZSBvZiBhIHNpbmdsZSBwaWVjZSBvZiBjYW5keSwgaW4gZG9sbGFycyBhbmQgaW4gdGhlIHNhbWUgZm9ybWF0IGFzIG0uIFRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSBjb250YWluaW5nICYjMzk7MCAwLjAwJiMzOTs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCBpbmRpY2F0aW5nIHRoZSBtYXhpbXVtIGFtb3VudCBvZiBjYWxvcmllcyB5b3UgY2FuIGJ1eSB3aXRoIHVwIHRvIG0gZG9sbGFycy4gT3V0cHV0IG5vIHNwYWNlcywgYW5kIGRvIG5vdCBzZXBhcmF0ZSBhbnN3ZXJzIHdpdGggYmxhbmsgbGluZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d