Torres y reinas
El problema de las ocho reinas es un reto clásico propuesto por primera vez a mediados del siglo XIX y que consiste en colocar en un tablero de ajedrez 8 reinas sin que se ataquen entre ellas.
Cuando llegaron las máquinas y la algoritmia el problema se extendió de tableros de 8×8 a tableros de cualquier tamaño, convirtiéndose así en el problemas de las N reinas. Hoy se sabe, por ejemplo, que para un tablero de 8×8 hay 92 posibles colocaciones (incluyendo simetrías) y que para uno de 16×16 superan los 14 millones.
Una vuelta de tuerca del problema es hacer que cada celda o escaque del tablero tenga un valor que se "puntúa" si se sitúa en ella alguna pieza. El objetivo pasa a ser encontrar la colocación de las reinas que maximice el valor total conseguido, entendido este por la suma de valores de las celdas en las que se han colocado reinas.
Y la última vuelta de tuerca es hacer lo mismo pero en lugar de colocar N reinas, colocar Q reinas y R torres.
Entrada
La entrada está formada por distintos casos de prueba.
Cada caso comienza con una línea con dos números indicando el número de reinas, Q, y el número de torres, R que hay que colocar (N = Q + R ≤ 8).
A continuación aparece la información del tablero: N líneas cada una con N números entre 1 y 1000 con el valor de cada escaque.
Salida
Por cada caso de prueba se escribirá una línea con el valor más alto que puede conseguirse colocando en el tablero Q reinas y R torres sin que se ataquen entre ellas.
Recuerda que en el ajedrez las reinas atacan a cualquier pieza que esté en la misma fila, columna o diagonal, mientras que las torres solo pueden moverse en línea recta en horizontal o vertical.
Entrada de ejemplo
1 2 1 3 0 4 0 0 1 1 0 1 1 10 10 10 10
Salida de ejemplo
7 0