Decatlón Vacuno.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

FrankHG

Problem types

Allowed languages

C, C++, Java, Pascal, Python, VB

Las $N$ ~N~ vacas del Granjero Juan, convenientemente denominadas $1...N$ ~1...N~ como siempre, se están preparando para una decatlón que tiene $N$ ~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$ ~i~ tiene un nivel de habilidad $s_{ij}$ ~s_{ij}~ cuando compite en el evento $j$ ~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$ ~B~ bonos que los jueces pueden dar. El Bono i tiene tres partes: si las vacas obtienen al menos $P_i$ ~P_i~ puntos para los primeros $K_i$ ~K_i~ eventos (incluyendo otros bonos involucrados en exactamente esos eventos) ellas obtendrán $A_i$ ~A_i~ puntos adicionales.

Por ejemplo, consideremos $N=3$ ~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)$ ~(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$ ~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$ ~N~, $B$ ~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$ ~K_i, P_i, A_i~.
Líneas B+2..B+N+1: La línea $B+1+j$ ~B+1+j~ contendrá la información de como será la actuación de la vaca $j$ ~j~ en cada uno de sus eventos. Esto será dado por $N$ ~N~ enteros separados por espacios: $S_{j1}..s_{jN}$ ~S_{j1}..s_{jN}~.