11559 - Event Planning

你被選為理事會的會長，負責舉辦這一次的遠足活動，你要選擇一個週末出遊，並選擇一間最便宜的旅館訂房。在有限的預算下，你希望所有會員都住在同一間旅館。

Input

輸入會有多組測試資料，每組資料的第一列有四個整數：1 <= N <= 200表示會員數，1 <= B <= 500,000表示預算總額，1 <= H <= 18表示可選擇的旅館總數，1 <= W <= 13表示有幾個可選擇的週末。接下來兩列一組共有H組旅館的資料，第一列為整數 p (1 <= 0 <= 10,000)表示旅館一人住一晚的費用，第二列有W個整數a，0 <= a <= 1000，表示旅館每個週末的空房數。

Output 

請針對每組測試資料，輸出最少的住宿費用，若所有旅館皆達不到要求，請輸出"stay home"。

Sample Input 

3 1000 2 3
200
0 2 2
300
27 3 20
5 2000 2 4
300
4 3 0 4
450
7 8 0 13

Sample Output 

900
stay home

---

原文出處