전국 대학생 프로그래밍 대회 동아리 연합

당신은 작년 '전국 대학생 프로그래밍 대회 동아리 연합'(이하 전대프연) 회의에 참석하지 않았고, 그 결과 올해 회장으로 선출되었다.

전대프연 회장은 가을에 오프라인 대회를 한 번 개최해야 한다. 대회를 열 주말은 자유롭게 고를 수 있으며, 회원들이 묵을 호텔도 하나 정해야 한다. 예산이 넉넉하지 않으므로 되도록 저렴한 호텔을 선택해야 한다.

규칙은 다음과 같다.

• 모든 회원은 반드시 같은 호텔에서 같은 주말에 묵어야 한다. (작년에는 회원들이 여러 호텔에 흩어져 묵다가 일부가 길을 잃는 사고가 있었다.)
• 선택한 호텔은 선택한 주에 모든 회원 $N$명을 수용할 수 있어야 한다.
• 여행의 총 비용은 예산 $B$를 초과할 수 없다. 총 비용은 (참가자 수) $\times$ (호텔의 일인당 숙박비용)으로 계산한다.

대회를 개최할 수 있는 방법 중에서 총 비용이 가장 작은 값을 구하라.

첫째 줄에 참가자 수 $N$ ($1 \le N \le 200$), 예산 $B$ ($1 \le B \le 500000$), 호텔의 수 $H$ ($1 \le H \le 18$), 고를 수 있는 주말의 수 $W$ ($1 \le W \le 13$)가 공백으로 구분되어 주어진다.

이어서 각 호텔의 정보가 두 줄씩 주어진다. 각 호텔의 첫 번째 줄에는 일인당 숙박비용 $p$ ($1 \le p \le 10000$)가 주어지고, 두 번째 줄에는 각 주에 투숙 가능한 인원 $a_1, a_2, \dots, a_W$ ($0 \le a_i \le 1000$)가 공백으로 구분되어 주어진다. 여기서 $a_i$는 $i$번째 주에 그 호텔에 묵을 수 있는 최대 인원이다.

대회를 개최할 수 있으면 최소 총 비용을 출력한다. 어떤 방법으로도 개최할 수 없으면 stay home을 출력한다.