시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 440 191 183 45.865%

문제

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

전대프연 회장은 오프라인 대회를 가을에 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjMjE4IDEgJmxlOyBOICZsZTsgMjAwLCBcdWM2MDhcdWMwYjAgMSAmbGU7IEIgJmxlOyA1MDAwMDAsIFx1ZDYzOFx1ZDE1NFx1Yzc1OCBcdWMyMTggMSAmbGU7IEggJmxlOyAxOCwgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOGZjXHVjNzU4IFx1YWMxY1x1YzIxOCAxICZsZTsgVyAmbGU7IDEzXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWFjMDEgXHVkNjM4XHVkMTU0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDYzOFx1ZDE1NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHVkNjM4XHVkMTU0XHVjNzU4IFx1Yzc3Y1x1Yzc3OFx1YjJmOSBcdWMyMTlcdWJjMTVcdWJlNDRcdWM2YTkgMSAmbGU7IHAgJmxlOyAxMDAwMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWM4ZmNcdWM1ZDAgXHVkMjJjXHVjMjE5IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3NzhcdWM2ZDAgMCAmbGU7IGEgJmxlOyAxMDAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWFjMWNcdWNkNWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNWM2XHVjNzNjXHViYTc0ICZxdW90O3N0YXkgaG9tZSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTA0NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV2ZW50IFBsYW5uaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5BcyB5b3UgZGlkbiYjMzk7dCBzaG93IHVwIHRvIHRoZSB5ZWFybHkgZ2VuZXJhbCBtZWV0aW5nIG9mIHRoZSBOb3JkaWMgQ2x1YiBvZiBQaW4gQ29sbGVjdG9ycywgeW91IHdlcmUgdW5hbmltb3VzbHkgZWxlY3RlZCB0byBvcmdhbml6ZSB0aGlzIHllYXJzIGV4Y3Vyc2lvbiB0byBQaW4gQ2l0eS4gWW91IGFyZSBmcmVlIHRvIGNob29zZSBmcm9tIGEgbnVtYmVyIG9mIHdlZWtlbmRzIHRoaXMgYXV0dW1uLCBhbmQgaGF2ZSB0byBmaW5kIGEgc3VpdGFibGUgaG90ZWwgdG8gc3RheSBhdCwgcHJlZmVyYWJseSBhcyBjaGVhcCBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgc29tZSBjb25zdHJhaW50czogVGhlIHRvdGFsIGNvc3Qgb2YgdGhlIHRyaXAgbXVzdCBiZSB3aXRoaW4gYnVkZ2V0LCBvZiBjb3Vyc2UuIEFsbCBwYXJ0aWNpcGFudHMgbXVzdCBzdGF5IGF0IHRoZSBzYW1lIGhvdGVsLCB0byBhdm9pZCBsYXN0IHllYXJzIGNhdGFzdHJvcGhlLCB3aGVyZSBzb21lIG1lbWJlcnMgZ290IGxvc3QgaW4gdGhlIGNpdHksIG5ldmVyIGJlaW5nIHNlZW4gYWdhaW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb25zaXN0cyBvZiBmb3VyIGludGVnZXJzOiAxICZsZTsgTiAmbGU7IDIwMCwgdGhlIG51bWJlciBvZiBwYXJ0aWNpcGFudHMsIDEgJmxlOyBCICZsZTsgNTAwMDAwLCB0aGUgYnVkZ2V0LCAxICZsZTsgSCAmbGU7IDE4LCB0aGUgbnVtYmVyIG9mIGhvdGVscyB0byBjb25zaWRlciwgYW5kIDEgJmxlOyBXICZsZTsgMTMsIHRoZSBudW1iZXIgb2Ygd2Vla3MgeW91IGNhbiBjaG9vc2UgYmV0d2Vlbi4gVGhlbiBmb2xsb3cgdHdvIGxpbmVzIGZvciBlYWNoIG9mIHRoZSBIIGhvdGVscy4gVGhlIGZpcnN0IGdpdmVzIDEgJmxlOyBwICZsZTsgMTAwMDAsIHRoZSBwcmljZSBmb3Igb25lIHBlcnNvbiBzdGF5aW5nIHRoZSB3ZWVrZW5kIGF0IHRoZSBob3RlbC4gVGhlIHNlY29uZCBjb250YWlucyBXIGludGVnZXJzLCAwICZsZTsgYSAmbGU7IDEwMDAsIGdpdmluZyB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBiZWRzIGZvciBlYWNoIHdlZWtlbmQgYXQgdGhlIGhvdGVsLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBjb3N0IG9mIHRoZSBzdGF5IGZvciB5b3VyIGdyb3VwLCBvciAmcXVvdDtzdGF5IGhvbWUmcXVvdDsgaWYgbm90aGluZyBjYW4gYmUgZm91bmQgd2l0aGluIHRoZSBidWRnZXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d