由于你没有出席北欧别针收藏者俱乐部的年度大会，所以大家一致推选你来组织今年的别针城之旅。

今年秋天，你可以在许多周末自由选择，并必须找到一个合适的酒店，最好是尽可能便宜的。

你有一些限制条件:

• 旅行的总费用必须在预算之内。

• 所有参与者必须住在同一家酒店，以避免去年的灾难，当时一些成员在城市中迷路，再也没有出现过。

输入格式

将输入若干组测试数据。

第一行输入由4个整数组成: $N,B,H,W$

$N$ 为总人数，$B$ 为预算， $H$ 为可以考虑的酒店数量，$W$ 为可以旅游的周数。

$1≤N≤200,1≤B≤500000,1≤H≤18,1≤W≤13$

以下 $2H$ 行，关于第 $H_i$ 个酒店的情况，占两行，第一行一个数字 $P$，为在此酒店人均的消费，第二行共 $W$ 个数字，表示第 $W_i$ 周此酒店的空余床位。 $1≤p≤10000,0≤W_i≤1000$

输出格式

一行。

若考虑之后的总费用在预算之内哦，则输出总费用。

如果超出了预算，则输出 "stay home"。