시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB104382357156823.161%

문제

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

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

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

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

입력

각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 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+XHJcblxyXG48cD5cdWI0NTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWIzYzhcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWMwMFx1YWM4Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWMxMWMgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YzBiMFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFkNmNcdWI5ZTRcdWQ1NWMgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1Y2U3Y1x1Yjg1Y1x1YjlhY1x1YWMwMCBcdWIzNTQgXHVkMDcwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWIwYjRcdWFlMzBcdWM1ZDBcdWMxMWMgXHVjNzc0XHVhZTMwXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzdhMFx1YzJkYyBcdWQ2NTRcdWM3YTVcdWMyZTRcdWM1ZDAgXHVhYzE0XHViMmU0XHVjNjI4XHViMmU0XHVhY2UwIFx1ZDU1MVx1YWNjNFx1Yjk3YyBcdWIzMDQgXHViNGE0XHVjNWQwLCBcdWIxNzhcdWQyYjhcdWJkODFcdWM3NDQgXHVjNWY0XHVhY2UwIFx1YzBhY1x1ZDBkNSBcdWFjMDBcdWFjOGNcdWM3NTggXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzQ0IFx1ZDU3NFx1ZDBiOVx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWMyZGNcdWMyYTRcdWQxNWNcdWM1ZDBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YzBhY1x1ZDBkNSBcdWFjMDBcdWFjOGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMDBcdWFjYTlcdWFjZmMgXHVjZTdjXHViODVjXHViOWFjXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWI0ZjFcdWM3YWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHViOWNlXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWMwYWNcdWQwZDVcdWM3NDQgXHVhZDZjXHViOWU0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjMGFjXHVkMGQ1XHVjNzQwIFx1Y2FiY1x1YWMyNCBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzdjXHViZDgwXHViOWNjIFx1YWQ2Y1x1YjllNFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWQwZDUgXHVhYzAwXHVhYzhjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1YWMwMFx1YWNhOVx1YWNmYyBcdWNlN2NcdWI4NWNcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU1OFx1YmE3NCBcdWNlN2NcdWI4NWNcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWQwNmNcdWFjOGMgXHViNDE4XHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWFjOGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNSBcdWM4ODVcdWI5NThcdWM3NTggXHVjMjE4IG5cdWFjZmMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViM2M4XHVjNzU4IFx1YzU5MSBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgNSwwMDAsIDAuMDEgJmxlOyBtICZsZTsgMTAwLjAwKSBtXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWMxOGNcdWMyMThcdWM4MTAgXHViNDU4XHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZTdjXHViODVjXHViOWFjIGNcdWM2NDAgXHVhYzAwXHVhY2E5IHBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGMgJmxlOyA1LDAwMCwgMC4wMSAmbGU7IHAgJmxlOyAxMDAuMDApIGNcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgxNVx1YzIxOCwgcFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOFx1Yzc5MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTswIDAuMDAmIzM5O1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViM2M4IG1cdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWQ2Y1x1YjllNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjZTdjXHViODVjXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0NzgxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FuZHkgU3RvcmUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgd2Fsa2luZyB3aXRoIGEgZnJpZW5kLCB3aGVuIHlvdSBwYXNzIGEgY2FuZHkgc3RvcmUuIFlvdSBtYWtlIGEgY29tbWVudCBhYm91dCBob3cgdW5oZWFsdGh5IHRoZWlyIHdhcmVzIGFyZS4gWW91ciBmcmllbmQgaXNzdWVzIGFuIGludGVyZXN0aW5nIGNoYWxsZW5nZTogd2hvIGNhbiBiZSB0aGUgdW5oZWFsdGhpZXN0PyBCb3RoIG9mIHlvdSB3aWxsIGdvIGludG8gdGhlIHN0b3JlIHdpdGggdGhlIHNhbWUgYW1vdW50IG9mIG1vbmV5LiBXaG9ldmVyIGJ1eXMgY2FuZHkgd2l0aCB0aGUgbW9zdCB0b3RhbCBjYWxvcmllcyB3aW5zITxcL3A+XHJcblxyXG48cD5TaW5jZSB5b3UmIzM5O3JlIGEgc21hcnQgY29tcHV0ZXIgc2NpZW50aXN0LCBhbmQgc2luY2UgeW91IGhhdmUgYWNjZXNzIHRvIHRoZSBjYW5keSBzdG9yZSYjMzk7cyBpbnZlbnRvcnksIHlvdSBkZWNpZGUgbm90IHRvIHRha2UgYW55IGNoYW5jZXMuIFlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgdGhlIG1vc3QgY2Fsb3JpZXMgeW91IGNhbiBidXkuIFRoZSBpbnZlbnRvcnkgdGVsbHMgeW91IHRoZSBwcmljZSBhbmQgY2Fsb3JpZXMgb2YgZXZlcnkgaXRlbS4gSXQgYWxzbyB0ZWxscyB5b3UgdGhhdCB0aGVyZSBpcyBzbyBtdWNoIGluIHN0b2NrIHRoYXQgeW91IGNhbiBidXkgYXMgbXVjaCBvZiBhbnkga2luZCBvZiBjYW5keSBhcyB5b3Ugd2FudC4gWW91IGNhbiBvbmx5IGJ1eSB3aG9sZSBwaWVjZXMgb2YgY2FuZHkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIG11bHRpcGxlIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggYSBsaW5lIHdpdGggYW4gaW50ZWdlciBuICgxJmxlO24mbGU7NSwwMDApLCBhbmQgYW4gYW1vdW50IG9mIG1vbmV5IG0gKCQwLjAxJmxlO20mbGU7JDEwMC4wMCksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB0eXBlcyBvZiBjYW5keSBmb3Igc2FsZSwgYW5kIG0gaXMgdGhlIGFtb3VudCBvZiBtb25leSB5b3UgaGF2ZSB0byBzcGVuZC4gVGhlIG1vbmV0YXJ5IGFtb3VudCBtIHdpbGwgYmUgZXhwcmVzc2VkIGluIGRvbGxhcnMgd2l0aCBleGFjdGx5IHR3byBkZWNpbWFsIHBsYWNlcywgYW5kIHdpdGggbm8gbGVhZGluZyB6ZXJvcyB1bmxlc3MgdGhlIGFtb3VudCBpcyBsZXNzIHRoYW4gb25lIGRvbGxhci4gVGhlcmUgd2lsbCBiZSBubyBkb2xsYXIgc2lnbi4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIHdpbGwgaGF2ZSBhbiBpbnRlZ2VyIGMgKDEmbGU7YyZsZTs1LDAwMCkgYW5kIGFuIGFtb3VudCBvZiBtb25leSBwICgkMC4wMSZsZTtwJmxlOyQxMDAuMDApLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIHdoZXJlIGMgaXMgdGhlIG51bWJlciBvZiBjYWxvcmllcyBpbiBhIHNpbmdsZSBwaWVjZSBvZiBjYW5keSwgYW5kIHAgaXMgdGhlIHByaWNlIG9mIGEgc2luZ2xlIHBpZWNlIG9mIGNhbmR5LCBpbiBkb2xsYXJzIGFuZCBpbiB0aGUgc2FtZSBmb3JtYXQgYXMgbS4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgJiMzOTswIDAuMDAmIzM5OzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIsIGluZGljYXRpbmcgdGhlIG1heGltdW0gYW1vdW50IG9mIGNhbG9yaWVzIHlvdSBjYW4gYnV5IHdpdGggdXAgdG8gbSBkb2xsYXJzLiBPdXRwdXQgbm8gc3BhY2VzLCBhbmQgZG8gbm90IHNlcGFyYXRlIGFuc3dlcnMgd2l0aCBibGFuayBsaW5lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d