Las N vacas del Granjero Juan ~(1 \leq N \leq 20)~, convenientemente denominadas ~1...N~ como siempre, se están preparando para una decatlón que tiene ~N~ eventos diferentes (entonces tal vez sería mejor llamarla N-atlón en vez de decatlón, la cual tradicionalmente tiene exactamente 10 eventos).

La vaca i tiene un nivel de habilidad ~s_{ij} (1 \leq s_{ij} \leq 1000)~ cuando compite en el evento ~j~. Cada vaca debe competir en un y único evento, y cada evento debe tener alguna vaca competiendo en él.

El puntaje total para todas las vacas es la suma de sus niveles de habilidad en los eventos en los cuales están competiendo. Sin embargo, los jurados del evento también pueden dar puntos de bonos si ellos son impresionados particularmente. Hay ~B~ bonos ~(1 \leq B \leq 20)~ que los jueces pueden dar. El Bono i tiene tres partes: si las vacas obtienen al menos ~P_i~ puntos ~(1 \leq P_i \leq 40,000)~ para los primeros ~K_i~ eventos (incluyendo otros bonos involucrados en exactamente esos eventos) ellas obtendrán ~A_i~ puntos adicionales ~(1 \leq A_i \leq 1000)~.

Por ejemplo, consideremos N = 3 vacas con las siguientes habilidades:

         E V E N T O 
         | 1 | 2 | 3
       --+---+---+--
    C  1 | 5 | 1 | 7
       --+---+---+--
    O  2 | 2 | 2 | 4
       --+---+---+--
    W  3 | 4 | 2 | 1

Por ejemplo, la vaca 1 podría obtener 7 puntos para el equipo si ella participara en el evento 3.

Suponga que los jueces ofrecen un bono (B = 1), tal que si las vacas obtienen al menos 7 puntos en los primeros dos eventos, ellas obtendrán 6 puntos adicionales. Aquí, la asignación óptima podría ser asignar la vaca 1 al evento 1, la vaca 2 al evento 3 y la vaca 3 al evento 2. Para los dos primeros eventos, la vaca 1 obtendrá 5 puntos y la vaca 3 obtendrá 2 puntos dándoles 7 puntos, lo cual es suficiente para satisfacer el bono 1. Por lo tanto, el puntaje total que ellas obtendrán será ~5+2+4+6=17~.

Por favor, decida en qué eventos deberían participar las vacas para maximizar su puntaje total.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~, ~B~

• Líneas 2..B+1: La línea i+1 contendrá la información para el bono i la cual está en tres enteros separados por espacios: ~K_i,P_i, A_i~.

• Líneas B+2..B+N+1: La línea ~B+1+j~ contendrá la información de como será la actuación de la vaca j en cada uno de sus eventos. Esto será dado por N enteros separados por espacios: ~ S_{j1}..s_{jN}~.

Ejemplo de Entrada

3 1
2 7 6
5 1 7
2 2 4
4 2 1

Salida

• Línea 1: La cantidad máxima de puntos que las vacas pueden recibir, incluyendo bonos.

Ejemplo de Salida

17

Detalles de la Salida

La vaca 1 participará en el evento 1, la vaca 3 participará en el evento 2 y la vaca 2 participará en el evento 3.