National Collegiate Programming Contest Club Federation

Because you missed last year's meeting of the National Collegiate Programming Contest Club Federation (hereafter "the Federation"), you were elected as this year's president.

The president must hold one offline contest in the fall. You may freely choose which weekend to hold it, and you must pick a single hotel where all members will stay. The budget is tight, so you should choose as cheap a hotel as possible.

The rules are as follows:

• Every member must stay at the same hotel on the same weekend. (Last year the members split across several hotels and some of them got lost.)
• The chosen hotel must be able to accommodate all $N$ members during the chosen week.
• The total cost of the trip may not exceed the budget $B$. The total cost equals (number of participants) $\times$ (the hotel's per-person price).

Among all valid options, find the smallest possible total cost.

The first line contains the number of participants $N$ ($1 \le N \le 200$), the budget $B$ ($1 \le B \le 500000$), the number of hotels $H$ ($1 \le H \le 18$), and the number of selectable weekends $W$ ($1 \le W \le 13$), separated by spaces.

Then the information for each hotel is given on two lines. The first line contains the per-person price $p$ ($1 \le p \le 10000$). The second line contains, separated by spaces, the guest capacities for each week $a_1, a_2, \dots, a_W$ ($0 \le a_i \le 1000$), where $a_i$ is the maximum number of people who can stay at that hotel during week $i$.

If the contest can be held, print the minimum total cost. If it cannot be held in any way, print stay home.