Equipos de programación balanceados solidariamente X71059

Una compañía multinacional participa cada año en las competiciones de programación CodeStrengths con unos cuantos equipos de programadores. Cuando organiza los equipos, siempre crea un primer equipo con los mejores programadores de la compañía, después un segundo equipo con los restantes mejores programadores de la compañía, y así sucesivamente.

Este año, con el ánimo de hacer un gesto en pro de la concordia y la solidaridad entre los pueblos del mundo, la compañía ha decidido formar equipos con solo programadores de su staff que sean Rusos y Estadounidenses, de modo que, si puede ser, los equipos esten formados por programadores de ambos grupos y de forma balanceada.

De todos modos, el primer criterio para formar un equipo continúa siendo el nivel de programación. Por ejemplo, el primer equipo no puede tener a un programador que sea peor que el de otro que no esté en el primer equipo.

Como segundo criterio, se intentará que el equipo a formar esté tan balanceado como sea posible. Por ejemplo, si los equipos están formados por cuatro personas, se prefiere un equipo con dos Rusos y dos Estadounidenses a un equipo con tres Rusos y un Estadounidense, y esto último es preferible a un equipo con cuatro Rusos y ningún Estadounidense.

Como último criterio, los programadores se escojen por nombre en orden lexicográfico (orden estandar de comparación entre strings).

Entrada

La entrada tiene varios casos. La primera linea de cada caso tiene un natural positivo k, que es el número de miembros de cada equipo a formar. En una segunda linea hay un natural positivo n₁, que es el número de programadores Rusos. Después vienen n₁ lineas, cada una con el nombre de un programador Ruso y un natural positivo indicando su nivel de programación. Estas lineas están ordenadas de mayor a menor por nivel de programación, y en orden lexicográfico para programadores con el mismo nivel. Después hay una nueva linea con un natural positivo n₂, que es el número de programadores Estadounidenses. Después vienen n₂ líneas con la información de los programadores Estadounidenses, siguiento exactamente el mismo formato que para los programadores Rusos.

Se garantiza que n₁+n₂ es múltiple de k, y que no hay repeticiones de nombres. En particular, un nombre de una lista no aparece en la otra lista.

Salida

Para cada caso, hay que escribir (n₁+n₂)/k lineas. La primera contendrá la lista de nombres del primer equipo en orden lexicográfico. La segunda contendrá la lista de nombres del segundo equipo en orden lexicográfico. I así sudesivamente. Después de la salida de cada caso hay una linea en blanco.

Observación

Evaluación sobre 10 puntos:

• Solución lenta: 5 puntos.
• Solución rápida: 10 puntos.

Entendemos como solución rápida una que es correcta, de coste lineal (se permite coste (n₁+n₂)log(k) para poder aplicar un sort a los miembros de cada equipo) y capaz de superar los juegos de pruebas públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de pruebas públicos.