Mike has grown extremely bored of playing snakes and ladders. So, with his mind cleared after a hike, Mike sat down and began devising his own board game!
The game involves a grid of cells, with each cell containing a non-negative integer. Initially, a token is placed on the top-left corner of the grid. Then, in one move, the token is moved to the cell directly to the right or down, with the token not allowed to move out of the grid. Moves are made until the token reaches the bottom-right corner. Then, the total score is the sum of the integers written in the cells visited by the token. The smaller the score, the better.
To make things more interesting, before the game starts, players are allowed to change the integer written on at most cells to . This allows them to potentially achieve lower scores.
Mike has constructed a grid with rows and columns, and wants you to help him answer queries. Denote as the cell in the -th row and -th column, and let be the integer written in cell . In the -th query, you have been asked to determine the smallest possible score if the game was to be played on the subgrid with the top-left corner of and bottom-right corner of , and . Each query is completely independent (updating the value of cells does not persist between queries), and the token must always lie within the relevant subgrid for each query.
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line contains three integers, .
The -th of the following lines contains integers, .
The -th of the following lines contains five integers, .
Print lines of output. The -th line should contain a single integer, representing the answer for the -th query.
2 3 2 2 3 5 4 1 8 1 1 1 3 1 1 2 2 3 1
In the first query, after updating the cell containing to contain , the token can visit the cell containing the integers in that order.
In the second query, after updating the cell containing to contain , the token can visit the cell containing the integers in that order.