4087 - Gorgeous Signs

Created by José Luis Castrillón Garrido
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 3000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Joseph was given an electric bike as an award for being a great student, he spends most of his time riding all along the city. The city where Joseph lives is very quiet and monotonous, and describes a perfect Manhattan city, where each block has the same length making the city look as a matrix of N rows and M columns. Each corner (intersection of blocks) of the city, have a sign with a beautiful painting on it. The beauty of a sign can be seen as an integer number from 0 to 100 where 0 indicates the ugliest painting and 100 means the most beautiful painting.

Joseph will start at cell (1, 1), and will end his journey at cell (N, M), as he is not a moron he will go on the shortest path to his destination, which means if he is located at cell (X, Y) his next cell will be either the one below (X + 1, Y) or the one to the right (X, Y + 1). Joseph doesn’t like so much turning his bike, he prefers going on straight paths because he gains more speed, so he will not tolerate to do more than K turns on his journey. A turn happens on two scenarios:
  1. His position is (X, Y) and his current direction is down (previous cell was (X - 1, Y) ), his next move is to the cell in the right (X, Y + 1).
  2. His position is (X, Y) and his current direction is right (previous cell was (X, Y - 1) ), his next move is to the cell below (X, Y + 1).
Taking into account that Joseph might start looking down or right at cell (1, 1) and this does not count as a turn, please help him take the path that maximizes the overall sum of beauty while making at most K turns.
A Joseph le dieron una bicicleta eléctrica como premio por ser un gran estudiante, y él pasa la mayor parte del tiempo montando a lo largo de la ciudad. La ciudad donde vive Joseph es muy tranquila y monótona, y describe una ciudad perfecta de Manhattan, donde cada bloque tiene la misma longitud, lo que hace que la ciudad se vea como una matriz de N filas y M columnas. Cada esquina (intersección de bloques) de la ciudad tiene un letrero con una hermosa pintura. La belleza de un signo se puede ver como un número entero de 0 a 100, donde 0 indica la pintura más fea y 100 significa la pintura más bella.

Joseph comenzará en la celda (1, 1) y terminará su viaje en la celda (N, M), y como no es tonto él irá por el camino más corto hacia su destino. Lo que significa que si se encuentra en la celda (X, Y) su siguiente celda será la que se encuentra debajo (X + 1, Y) o la de la derecha (X, Y + 1). A Joseph no le gusta tanto girar su bicicleta, prefiere ir por senderos rectos porque gana más velocidad, por lo que no tolerará hacer más de K giros en su viaje. Un giro sucede en dos escenarios:
  1. Su posición es (X, Y) y su dirección actual es hacia abajo (la celda anterior era (X - 1, Y)), su próximo movimiento es hacia la celda de la derecha (X, Y + 1).
  2. Su posición es (X, Y) y su dirección actual es a la derecha (la celda anterior era (X, Y - 1)), su siguiente movimiento es hacia la celda de abajo (X, Y + 1).
Teniendo en cuenta que Joseph podría comenzar a mirar hacia abajo o hacia la derecha en la celda (1, 1) y esto no cuenta como un giro, ayúdelo a tomar el camino que maximiza la suma total de belleza mientras realiza como máximo K turnos.
Joseph was given an electric bike as an award for being a great student, he spends most of his time riding all along the city. The city where Joseph lives is very quiet and monotonous, and describes a perfect Manhattan city, where each block has the same length making the city look as a matrix of N rows and M columns. Each corner (intersection of blocks) of the city, have a sign with a beautiful painting on it. The beauty of a sign can be seen as an integer number from 0 to 100 where 0 indicates the ugliest painting and 100 means the most beautiful painting.

Joseph will start at cell (1, 1), and will end his journey at cell (N, M), as he is not a moron he will go on the shortest path to his destination, which means if he is located at cell (X, Y) his next cell will be either the one below (X + 1, Y) or the one to the right (X, Y + 1). Joseph doesn’t like so much turning his bike, he prefers going on straight paths because he gains more speed, so he will not tolerate to do more than K turns on his journey. A turn happens on two scenarios:
  1. His position is (X, Y) and his current direction is down (previous cell was (X - 1, Y) ), his next move is to the cell in the right (X, Y + 1).
  2. His position is (X, Y) and his current direction is right (previous cell was (X, Y - 1) ), his next move is to the cell below (X, Y + 1).
Taking into account that Joseph might start looking down or right at cell (1, 1) and this does not count as a turn, please help him take the path that maximizes the overall sum of beauty while making at most K turns.

Input specification

The first line of input contains the number of test cases T (1 <= T <= 20), each test case begins with a line containing three integers indicating the number of rows N, the number of columns M and the maximum possible number of turns K such that 1 <= N, M <= 50, 0 <= K < N + M. Each of the next N lines contains the description of a row in the matrix that describes the city. So, each line will contain M integers, one for each column of the matrix. All the values in the matrix will range from 0 to 100.
La primera línea de entrada contiene el número de casos de prueba T (1 <= T <= 20), cada caso de prueba comienza con una línea que contiene tres enteros que indican el número de filas N, el número de columnas M y el número máximo posible de giros K tal que 1 <= N, M <= 50, 0 <= K < N + M. Cada una de las siguientes N líneas contiene la descripción de una fila en la matriz que describe la ciudad. Entonces, cada línea contendrá M enteros, uno para cada columna de la matriz. Todos los valores en la matriz variarán de 0 a 100.

The first line of input contains the number of test cases T (1 <= T <= 20), each test case begins with a line containing three integers indicating the number of rows N, the number of columns M and the maximum possible number of turns K such that 1 <= N, M <= 50, 0 <= K < N + M. Each of the next N lines contains the description of a row in the matrix that describes the city. So, each line will contain M integers, one for each column of the matrix. All the values in the matrix will range from 0 to 100.

Output specification

For each test case output the best possible beauty Joseph can see in an optimal way that doesn't makes more than K turns. If it is not possible to do the journey, output -1 instead.
Para cada salida de caso de prueba, la mejor belleza posible que Joseph puede ver de una manera óptima que no genera más de K vueltas. Si no es posible hacer el viaje, salida -1 en su lugar.

The first line of input contains the number of test cases T (1 <= T <= 20), each test case begins with a line containing three integers indicating the number of rows N, the number of columns M and the maximum possible number of turns K such that 1 <= N, M <= 50, 0 <= K < N + M. Each of the next N lines contains the description of a row in the matrix that describes the city. So, each line will contain M integers, one for each column of the matrix. All the values in the matrix will range from 0 to 100.

Sample input

1
4 4 1
4 5 2 1
2 3 2 2
1 6 6 2
7 1 2 3

Sample output

20

Hint(s)

Joseph can make only 1 turn, so he starts with the direction to the bottom at (1, 1), goes straight until the cell (N, 1), then turns and goes straight again until the bottom right corner of the matrix (N, M). The path is the one marked bold below.
4 5 2 1
2 3 2 2
1 6 6 2
7 1 2 3
Joseph solo puede hacer 1 vuelta, por lo que comienza con la dirección hacia abajo en (1, 1), va recto hasta la celda (N, 1), luego gira y va recto otra vez hasta la esquina inferior derecha de la matriz (N,M). La ruta es la marcada en negrita a continuación.
4 5 2 1
2 3 2 2
1 6 6 2
7 1 2 3
Joseph can make only 1 turn, so he starts with the direction to the bottom at (1, 1), goes straight until the cell (N, 1), then turns and goes straight again until the bottom right corner of the matrix (N, M). The path is the one marked bold below.
4 5 2 1
2 3 2 2
1 6 6 2
7 1 2 3