Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Incluso los genios millonarios tienen un mal día. El fin de semana llegó y Tony se disponía a demostrar que P=NP cuando su criatura Ultron, la inteligencia artificial, se apoderó de Jarvis. Pero las operaciones en Stark Industries deben continuar!. Tony tendrá que liberar algunos servidores. El ha dividido las tareas existentes en K tipos distintos y tomó N servidores. El costo de realizar una tarea de cada tipo es conocido para cada servidor que es capaz de realizar una tarea de este tipo.

Cada servidor puede ser configurado para realizar una tarea de un solo tipo. El provedor debe ser contactado para alterar la configuración de los servidores. Cualquier número de servidores puede ser configurado por un solo pedido. Cada pedido tiene un costo y toma un tiempo, es por eso que solo se puede hacer un pedido diario. Por razones técnicas la configuración de los servidores debe hacerse en las mañanas.

Tony ha planeado los cómputos de varios días. Ha planeado cuantas tareas de cada tipo se deben realizar en cada día. Es necesario el plan que minimice el costo total.

Input

La primera línea contene tres enteros $N, K, C$, cantidad de sevidores, número de tipos de tareas y costo del pedido de reconfiguración de servidores respectivamente $(1 <= K <= N <= 15, 0 <= C <= 10^5)$.

La siguiente línea contiene un entero $M (1 <= M <= N * K)$, luego $M$ líneas conteniendo tres enteros cada una:

$S, T, W$, donde $W$ es el conto de realizar una tarea de tipo $T$ en el servidor $S(1 <= S <= N, 1 <= T <= K,1 <= W <= 1000)$.

Luego vendrá una línea con el entero $Q (1 <= Q <= 100)$, la cantidad de días que contiene el plan.

Cada una de las siguientes $Q$ líneas consiste de $K$ enteros $a_1, a_2, ...., a_k$, donde $a_i$ es la cantidad de tareas del tipo $i$ que se deben realizar en este día. $(0 <= a_i <= 100)$

Se garantiza que existe una solución para cada caso.

Output

Imprima un número, menor costo posible de realizar todas las tareas del plan incluyendo la reconfiguración de servidores.

Sample test(s)