АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Жил бүр уламжлал болон зохиогддог олон улсын эдийн засгийн хурлыг зохион байгуулах хүндтэй үүрэг энэ жил танд ноогдож байна. Та хурлыг энэ зуны долоо хоногийн аль нэгэнд нь зохион байгуулах ёстой бөгөөд олон улсаас танай хотод хүмүүс ирж байгаа учраас та мөн хамгийн хямд бөгөөд бүх хүмүүсийг байрлуулахад тохиромжтой буудал олох ёстой.

Та мэдээж хурлын бүх зардлыг төсөвтөө багтаах ёстой. Мөн зарим зочдыг төөрөхөөс сэргийлэхийн тулд бүх зочдыг нэг буудалд байрлуулах ёстой.

Input

Оролт нь хэд хэдэн тестээс бүрдэнэ. Тест бүрийн эхний мөрөнд 4 бүхэл тоо өгөгдөнө. Эдгээр нь : зочдын тоо болох 1<=N<=200, Танд олгогдсон төсөв болох 1<=B<=500000, хотын буудлын тоо болох 1<=H<=18, таны сонгож болох долоо хоногийн тоо болох 1<=W<=13. Дараа нь буудлын тоогоор 2 мөр өгөгдөнө. Эхний мөрөнд нэг хүний буудалд байрлахад шаардагдах мөнгө 1<=p<=10000. Хоёр дахь мөрөнд W ширхэг бүхэл тоо өгөгдөнө. Энэ нь харгалзах долоо хоногт сул байх буудлын орны тоо.

Output

Тест бүрт нэг мөрөнд зочдыг байрлуулахад шаардагдах хамгийн бага мөнгөний хэмжээ төсөвтөө багтаж байвал тэр утгыг, хэрвээ төсвөөс хэтэрч байвал “stay home” гэж гаргана.

Example

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

Output:

900

stay home