시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 703 287 274 44.265%

문제

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

전대프연 회장은 오프라인 대회를 가을에 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+XHVjNWVjXHVkNTg5XHVjNzU4IFx1Y2QxZCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjNjA4XHVjMGIwXHVjNzQ0IFx1Y2QwOFx1YWNmY1x1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVkNjhjXHVjNmQwXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWQ2MzhcdWQxNTRcdWM1ZDBcdWMxMWMgXHViYTM4XHViYjNjXHViN2VjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzkxXHViMTQ0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWQ2OGNcdWM2ZDBcdWM3NzQgXHVhYzE5XHVjNzQwIFx1ZDYzOFx1ZDE1NFx1YzVkMCBcdWJhMzhcdWJiMzRcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNTU4XHVhY2UwLCBcdWM3NzRcdWI4NWNcdWM3NzhcdWQ1NzQgXHViMzAwXHVjN2FjXHVjNTU5XHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjBhY1x1YjJlNC4gXHVjNzdjXHViZDgwIFx1ZDY4Y1x1YzZkMFx1Yzc0MCBcdWFlMzhcdWM3NDQgXHVjNzgzXHVjNWI0XHViYzg0XHViODM4XHVhY2UwLCBcdWM1NDRcdWM5YzFcdWFlNGNcdWM5YzAgXHVhZGY4XHViNGU0XHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWJjZjggXHVjMGFjXHViNzhjXHVjNzQwIFx1YzVjNlx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YzIxOCAxICZsZTsgTiAmbGU7IDIwMCwgXHVjNjA4XHVjMGIwIDEgJmxlOyBCICZsZTsgNTAwMDAwLCBcdWQ2MzhcdWQxNTRcdWM3NTggXHVjMjE4IDEgJmxlOyBIICZsZTsgMTgsIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzhmY1x1Yzc1OCBcdWFjMWNcdWMyMTggMSAmbGU7IFcgJmxlOyAxM1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgXHVhYzAxIFx1ZDYzOFx1ZDE1NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWQ2MzhcdWQxNTRcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1ZDYzOFx1ZDE1NFx1Yzc1OCBcdWM3N2NcdWM3NzhcdWIyZjkgXHVjMjE5XHViYzE1XHViZTQ0XHVjNmE5IDEgJmxlOyBwICZsZTsgMTAwMDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHVjOGZjXHVjNWQwIFx1ZDIyY1x1YzIxOSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzc4XHVjNmQwIDAgJmxlOyBhICZsZTsgMTAwMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YzVjNlx1YzczY1x1YmE3NCAmcXVvdDtzdGF5IGhvbWUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUwNDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFdmVudCBQbGFubmluZyIsImRlc2NyaXB0aW9uIjoiPHA+QXMgeW91IGRpZG4mIzM5O3Qgc2hvdyB1cCB0byB0aGUgeWVhcmx5IGdlbmVyYWwgbWVldGluZyBvZiB0aGUgTm9yZGljIENsdWIgb2YgUGluIENvbGxlY3RvcnMsIHlvdSB3ZXJlIHVuYW5pbW91c2x5IGVsZWN0ZWQgdG8gb3JnYW5pemUgdGhpcyB5ZWFycyBleGN1cnNpb24gdG8gUGluIENpdHkuIFlvdSBhcmUgZnJlZSB0byBjaG9vc2UgZnJvbSBhIG51bWJlciBvZiB3ZWVrZW5kcyB0aGlzIGF1dHVtbiwgYW5kIGhhdmUgdG8gZmluZCBhIHN1aXRhYmxlIGhvdGVsIHRvIHN0YXkgYXQsIHByZWZlcmFibHkgYXMgY2hlYXAgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIHNvbWUgY29uc3RyYWludHM6IFRoZSB0b3RhbCBjb3N0IG9mIHRoZSB0cmlwIG11c3QgYmUgd2l0aGluIGJ1ZGdldCwgb2YgY291cnNlLiBBbGwgcGFydGljaXBhbnRzIG11c3Qgc3RheSBhdCB0aGUgc2FtZSBob3RlbCwgdG8gYXZvaWQgbGFzdCB5ZWFycyBjYXRhc3Ryb3BoZSwgd2hlcmUgc29tZSBtZW1iZXJzIGdvdCBsb3N0IGluIHRoZSBjaXR5LCBuZXZlciBiZWluZyBzZWVuIGFnYWluLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29uc2lzdHMgb2YgZm91ciBpbnRlZ2VyczogMSAmbGU7IE4gJmxlOyAyMDAsIHRoZSBudW1iZXIgb2YgcGFydGljaXBhbnRzLCAxICZsZTsgQiAmbGU7IDUwMDAwMCwgdGhlIGJ1ZGdldCwgMSAmbGU7IEggJmxlOyAxOCwgdGhlIG51bWJlciBvZiBob3RlbHMgdG8gY29uc2lkZXIsIGFuZCAxICZsZTsgVyAmbGU7IDEzLCB0aGUgbnVtYmVyIG9mIHdlZWtzIHlvdSBjYW4gY2hvb3NlIGJldHdlZW4uIFRoZW4gZm9sbG93IHR3byBsaW5lcyBmb3IgZWFjaCBvZiB0aGUgSCBob3RlbHMuIFRoZSBmaXJzdCBnaXZlcyAxICZsZTsgcCAmbGU7IDEwMDAwLCB0aGUgcHJpY2UgZm9yIG9uZSBwZXJzb24gc3RheWluZyB0aGUgd2Vla2VuZCBhdCB0aGUgaG90ZWwuIFRoZSBzZWNvbmQgY29udGFpbnMgVyBpbnRlZ2VycywgMCAmbGU7IGEgJmxlOyAxMDAwLCBnaXZpbmcgdGhlIG51bWJlciBvZiBhdmFpbGFibGUgYmVkcyBmb3IgZWFjaCB3ZWVrZW5kIGF0IHRoZSBob3RlbC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gY29zdCBvZiB0aGUgc3RheSBmb3IgeW91ciBncm91cCwgb3IgJnF1b3Q7c3RheSBob21lJnF1b3Q7IGlmIG5vdGhpbmcgY2FuIGJlIGZvdW5kIHdpdGhpbiB0aGUgYnVkZ2V0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==