Como Ud. no se presentó a la reunión general anual de su Grupo Social, usted fue elegido por unanimidad para organizar este año la excursión a Uyuni. Usted libremente puede elegir entre uno de los fines de semana de este verano y tiene que encontrar un lugar adecuado para alojarse, preferentemente lo más económico posible. Usted tiene algunas limitaciones: Por supuesto, el costo total del viaje debe estar dentro del presupuesto. Todos los participantes deben estar en el mismo hotel, para evitar la catástrofe del último año, donde algunos miembros se perdieron y nunca más se los volvió a encontrar.

El archivo de entrada contiene varios casos de prueba, cada uno de ellos se describe a continuación. La primera línea de entrada consta de cuatro enteros: el número de participantes 1 ≤ N ≤ 200, el presupuesto 1 ≤ P ≤ 500000, el número de hoteles a considerar 1 ≤ H ≤ 18 y el número de semanas que el grupo tiene disponible para la excursión, 1 ≤ S ≤ 13. Luego siguen dos líneas para cada uno de los H hoteles. La primera contiene el precio por persona del hospedaje del fin de semana en el hotel, 1 ≤ p ≤ 10000. La segunda contiene S números enteros, 0 ≤ s ≤ 1000, donde cada número representa al número de camas disponibles en ese fin de semana en el hotel.

Para cada caso de prueba, imprima en la salida el costo mínimo del hospedaje de su grupo (para un solo fin de semana) o “quedarse en casa” si no alcanza el presupuesto, en una sola línea.

La cantidad de camas disponibles sea mayor igual al número de participantes, tomar el menor de los costos.