시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 351 158 152 47.950%

문제

백준이는 작년 전국 대학생 프로그래밍 대회 동아리 연합(이하 전대프연) 회의에 불참했기 때문에, 올해 회장으로 선출되었다.

전대프연 회장은 오프라인 대회를 가을에 1회 개최해야 한다. 백준이는 대회를 개최할 주말을 마음대로 고를 수 있고, 회원들이 머무를 호텔을 찾아야 한다. 전대프연의 자금 사정은 넉넉하지 않기 때문에, 되도록 싼 호텔을 찾아야 한다.

여행의 총 비용은 예산을 초과하면 안된다. 모든 회원은 같은 호텔에서 머물러야 한다. 작년에 모든 회원이 같은 호텔에 머무르지 않았고, 이로인해 대재앙이 일어났다. 일부 회원은 길을 잃어버렸고, 아직까지 그들을 다시 본 사람은 없다. 

입력

첫째 줄에 참가자의 수 1 ≤ N ≤ 200, 예산 1 ≤ B ≤ 500000, 호텔의 수 1 ≤ H ≤ 18, 고를 수 있는 주의 개수 1 ≤ W ≤ 13이 주어진다. 다음 줄부터 각 호텔의 정보가 주어지며, 호텔의 정보는 두 줄로 이루어져 있다. 첫번째 줄에는 그 호텔의 일인당 숙박비용 1 ≤ p ≤ 10000이 주어지고, 둘째 줄에는 i번째 주에 투숙 가능한 인원 0 ≤ a ≤ 1000이 주어진다.

출력

첫째 줄에 대회를 개최할 수 있으면 최소 비용을 출력하고, 없으면 "stay home"을 출력한다.

예제 입력 1

3 1000 2 3
200
0 2 2
300
27 3 20

예제 출력 1

900

힌트

W3sicHJvYmxlbV9pZCI6IjUwNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWFkNmQgXHViMzAwXHVkNTU5XHVjMGRkIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGMgXHViM2Q5XHVjNTQ0XHViOWFjIFx1YzVmMFx1ZDU2OSIsImRlc2NyaXB0aW9uIjoiPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1Yzc5MVx1YjE0NCBcdWM4MDRcdWFkNmQgXHViMzAwXHVkNTU5XHVjMGRkIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGMgXHViM2Q5XHVjNTQ0XHViOWFjIFx1YzVmMFx1ZDU2OShcdWM3NzRcdWQ1NTggXHVjODA0XHViMzAwXHVkNTA0XHVjNWYwKSBcdWQ2OGNcdWM3NThcdWM1ZDAgXHViZDg4XHVjYzM4XHVkNTg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNjJjXHVkNTc0IFx1ZDY4Y1x1YzdhNVx1YzczY1x1Yjg1YyBcdWMxMjBcdWNkOWNcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1YjMwMFx1ZDUwNFx1YzVmMCBcdWQ2OGNcdWM3YTVcdWM3NDAgXHVjNjI0XHVkNTA0XHViNzdjXHVjNzc4IFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWFjMDBcdWM3NDRcdWM1ZDAgMVx1ZDY4YyBcdWFjMWNcdWNkNWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHViMzAwXHVkNjhjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU2MCBcdWM4ZmNcdWI5ZDBcdWM3NDQgXHViOWM4XHVjNzRjXHViMzAwXHViODVjIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWQ2OGNcdWM2ZDBcdWI0ZTRcdWM3NzQgXHViYTM4XHViYjM0XHViOTdjIFx1ZDYzOFx1ZDE1NFx1Yzc0NCBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM4MDRcdWIzMDBcdWQ1MDRcdWM1ZjBcdWM3NTggXHVjNzkwXHVhZTA4IFx1YzBhY1x1YzgxNVx1Yzc0MCBcdWIxMDlcdWIxMDlcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNDE4XHViM2M0XHViODVkIFx1YzJmYyBcdWQ2MzhcdWQxNTRcdWM3NDQgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHVkNTg5XHVjNzU4IFx1Y2QxZCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjNjA4XHVjMGIwXHVjNzQ0IFx1Y2QwOFx1YWNmY1x1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWQ2OGNcdWM2ZDBcdWM3NDAgXHVhYzE5XHVjNzQwIFx1ZDYzOFx1ZDE1NFx1YzVkMFx1YzExYyBcdWJhMzhcdWJiM2NcdWI3ZWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3OTFcdWIxNDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1ZDY4Y1x1YzZkMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVkNjM4XHVkMTU0XHVjNWQwIFx1YmEzOFx1YmIzNFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM1NThcdWFjZTAsIFx1Yzc3NFx1Yjg1Y1x1Yzc3OFx1ZDU3NCBcdWIzMDBcdWM3YWNcdWM1NTlcdWM3NzQgXHVjNzdjXHVjNWI0XHViMGFjXHViMmU0LiBcdWM3N2NcdWJkODAgXHVkNjhjXHVjNmQwXHVjNzQwIFx1YWUzOFx1Yzc0NCBcdWM3ODNcdWM1YjRcdWJjODRcdWI4MzhcdWFjZTAsIFx1YzU0NFx1YzljMVx1YWU0Y1x1YzljMCBcdWFkZjhcdWI0ZTRcdWM3NDQgXHViMmU0XHVjMmRjIFx1YmNmOCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNWM2XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjMjE4IDEgJmxlOyBOICZsZTsgMjAwLCBcdWM2MDhcdWMwYjAgMSAmbGU7IEIgJmxlOyA1MDAwMDAsIFx1ZDYzOFx1ZDE1NFx1Yzc1OCBcdWMyMTggMSAmbGU7IEggJmxlOyAxOCwgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOGZjXHVjNzU4IFx1YWMxY1x1YzIxOCAxICZsZTsgVyAmbGU7IDEzXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWFjMDEgXHVkNjM4XHVkMTU0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDYzOFx1ZDE1NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOCBcdWQ2MzhcdWQxNTRcdWM3NTggXHVjNzdjXHVjNzc4XHViMmY5IFx1YzIxOVx1YmMxNVx1YmU0NFx1YzZhOSAxICZsZTsgcCAmbGU7IDEwMDAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzhmY1x1YzVkMCBcdWQyMmNcdWMyMTkgXHVhYzAwXHViMmE1XHVkNTVjIFx1Yzc3OFx1YzZkMCAwICZsZTsgYSAmbGU7IDEwMDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMzAwXHVkNjhjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWM1YzZcdWM3M2NcdWJhNzQgJnF1b3Q7c3RheSBob21lJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXZlbnQgUGxhbm5pbmciLCJkZXNjcmlwdGlvbiI6IjxwPkFzIHlvdSBkaWRuJiMzOTt0IHNob3cgdXAgdG8gdGhlIHllYXJseSBnZW5lcmFsIG1lZXRpbmcgb2YgdGhlIE5vcmRpYyBDbHViIG9mIFBpbiBDb2xsZWN0b3JzLCB5b3Ugd2VyZSB1bmFuaW1vdXNseSBlbGVjdGVkIHRvIG9yZ2FuaXplIHRoaXMgeWVhcnMgZXhjdXJzaW9uIHRvIFBpbiBDaXR5LiBZb3UgYXJlIGZyZWUgdG8gY2hvb3NlIGZyb20gYSBudW1iZXIgb2Ygd2Vla2VuZHMgdGhpcyBhdXR1bW4sIGFuZCBoYXZlIHRvIGZpbmQgYSBzdWl0YWJsZSBob3RlbCB0byBzdGF5IGF0LCBwcmVmZXJhYmx5IGFzIGNoZWFwIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSBzb21lIGNvbnN0cmFpbnRzOiBUaGUgdG90YWwgY29zdCBvZiB0aGUgdHJpcCBtdXN0IGJlIHdpdGhpbiBidWRnZXQsIG9mIGNvdXJzZS4gQWxsIHBhcnRpY2lwYW50cyBtdXN0IHN0YXkgYXQgdGhlIHNhbWUgaG90ZWwsIHRvIGF2b2lkIGxhc3QgeWVhcnMgY2F0YXN0cm9waGUsIHdoZXJlIHNvbWUgbWVtYmVycyBnb3QgbG9zdCBpbiB0aGUgY2l0eSwgbmV2ZXIgYmVpbmcgc2VlbiBhZ2Fpbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnNpc3RzIG9mIGZvdXIgaW50ZWdlcnM6IDEgJmxlOyBOICZsZTsgMjAwLCB0aGUgbnVtYmVyIG9mIHBhcnRpY2lwYW50cywgMSAmbGU7IEIgJmxlOyA1MDAwMDAsIHRoZSBidWRnZXQsIDEgJmxlOyBIICZsZTsgMTgsIHRoZSBudW1iZXIgb2YgaG90ZWxzIHRvIGNvbnNpZGVyLCBhbmQgMSAmbGU7IFcgJmxlOyAxMywgdGhlIG51bWJlciBvZiB3ZWVrcyB5b3UgY2FuIGNob29zZSBiZXR3ZWVuLiBUaGVuIGZvbGxvdyB0d28gbGluZXMgZm9yIGVhY2ggb2YgdGhlIEggaG90ZWxzLiBUaGUgZmlyc3QgZ2l2ZXMgMSAmbGU7IHAgJmxlOyAxMDAwMCwgdGhlIHByaWNlIGZvciBvbmUgcGVyc29uIHN0YXlpbmcgdGhlIHdlZWtlbmQgYXQgdGhlIGhvdGVsLiBUaGUgc2Vjb25kIGNvbnRhaW5zIFcgaW50ZWdlcnMsIDAgJmxlOyBhICZsZTsgMTAwMCwgZ2l2aW5nIHRoZSBudW1iZXIgb2YgYXZhaWxhYmxlIGJlZHMgZm9yIGVhY2ggd2Vla2VuZCBhdCB0aGUgaG90ZWwuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtaW5pbXVtIGNvc3Qgb2YgdGhlIHN0YXkgZm9yIHlvdXIgZ3JvdXAsIG9yICZxdW90O3N0YXkgaG9tZSZxdW90OyBpZiBub3RoaW5nIGNhbiBiZSBmb3VuZCB3aXRoaW4gdGhlIGJ1ZGdldC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=