B. Pagos al final del viaje
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Es la final de la OIE y, un año más, Jacobo ha pagado más de lo que le tocaba y todo el mundo debe hacerle transferencias para saldar las cuentas. Pero claro, esto es lioso, ya que Blanca también ha adelantado el dinero de las comidas, Manu ha comprado los refrescos, etc.

Darío sugiere usar Splitwise, una aplicación en la que los n voluntarios apuntan cuánto han pagado cada vez que hacen una compra. Al final del viaje, esta aplicación suma cuánto ha pagado cada uno y, usando un algoritmo inteligente, organiza las transferencias para que cada voluntario acabe pagando lo mismo. Además, con este algoritmo, saldar las cuentas requiere como máximo n - 1 transferencias. ¿Sabrías diseñar un algoritmo semejante?

Input

Recibirás una línea en la entrada con un entero T, el número de casos que has de procesar. Cada caso consistirá en:

  • Una línea con dos enteros n y m: el número de voluntarios y el número de compras hechas en el viaje, respectivamente.
  • Una línea con n cadenas de caracteres: los nombres de los voluntarios.
  • m líneas, cada una con dos valores: si, el nombre del voluntario que hizo el i-ésimo pago; y ci, un entero que representa la cuantía de ese pago en céntimos.
Output

Por cada caso de prueba, imprime una línea con un entero p: el número de transferencias con el que se podrían saldar todas las cuentas. p debe ser menor o igual que n - 1. Después, imprime p líneas (una por transferencia, en cualquier orden), donde describas (1) quién hace la transferencia, (2) quién la recibe y (3) de qué valor es la transferencia (un valor estrictamente positivo). Observa que no es necesario minimizar el número de transferencias, pero este debe ser como máximo n - 1. Cualquier solución que cumpla estas restricciones será válida.

Scoring
  1. (10 puntos) Se necesitará exactamente una transferencia para saldar las cuentas.
  2. (15 puntos) Como máximo, dos transferencias serán suficientes para saldar las cuentas.
  3. (19 puntos) n ≤ 1000 y m ≤ 1000.
  4. (21 puntos) Cada voluntario ha hecho, como mucho, un pago.
  5. (35 puntos) Sin restricciones adicionales.
Example
Input
3
4 1
Jacobo Marco Pedro Joan
Jacobo 400
2 3
Jacobo Marco
Jacobo 1
Jacobo 2
Marco 3
3 3
dario manu alberto
dario 4
manu 5
alberto 6
Output
3
Joan Jacobo 100
Pedro Jacobo 100
Marco Jacobo 100
0
1
dario alberto 1
Note
  • 1 ≤ T ≤ 100
  • 2 ≤ n ≤ 50.000
  • 1 ≤ m ≤ 50.000
  • 1 ≤ ci ≤ 10.000
  • En cada caso de prueba, la suma de las ci es múltiplo de n. Es decir, se garantiza que hay una solución.
  • Los nombres de los voluntarios tendrán entre 1 y 20 caracteres, todos ellos en el alfabeto inglés. En cada caso de prueba, todos los nombres serán distintos entre sí.
  • La suma de las n de todos los casos de prueba en un mismo archivo no superará 50.000.
  • La suma de las m de todos los casos de prueba en un mismo archivo no superará 50.000.