Vamos plantear un juego muy sencillo. Se le da una matriz N × N inicialmente ocupado por ceros. Todas las celdas de las filas y columnas de esta matriz serán enumeradas de 1 a N, inclusive. Hay solo dos tipos de operaciones que usted puede aplicar sobre la matriz:

AddRow R X : Todos los números en la fila R deben aumentarse en X.
RowCol C X : Todos los números en la columna C se deben aumentar en X.

Ahora, después de realizado todas las operaciones se necesita encontrar el elemento máximo en la cuadrícula. ¿Sencillo verdad? Por eso se llama un juego fácil.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La primera línea de cada entrada contiene dos enteros separados por espacios N y Q denotan el tamaño de la cuadrícula y el número de operaciones a realizar.

Cada uno de los siguientes Q líneas describen una operación en el formato descrito anteriormente.

Restricciones.

1 ≤ N ≤ 4000
1 ≤ Q ≤ 4000
1 ≤ X ≤ 1000
1 ≤ R, C ≤ N

Output

Salida para cada caso. Una sola línea que contiene el número máximo encontrado en la matriz después de realizadas todas las operaciones.

Entrada de ejemplo

Explicación

La matriz cambia de la siguiente manera:

00 33 34 74 74
00 00 01 41 52

El número máximo en la matriz final es 7.