#439. Rise in Price
Rise in Price
Description
There are cells on a grid, the top-left cell is at while the bottom-right cell is at . You start at and move to . At any cell , you can move to or , provided that you don't move out of the grid. Clearly, you will make exactly steps.
When you are at cell , including the starting point and the destination , you can take all the diamonds at this cell, and have a chance to raise the price of each diamond by dollars. You will sell all the diamonds you have with the final price in the end, and your goal is to choose the optimal path that will maximize your profits. Note that initially the price of each diamond is zero, and you have nothing to sell.
Format
Input
The first line contains a single integer (), the number of test cases. For each test case:
The first line contains a single integer (), denoting the size of the grid.
Each of the following lines contains integers, the -th line contains (), denoting the number of diamonds in each cell.
Each of the following lines contains integers, the -th line contains (), denoting how much you can raise the price in each cell.
It is guaranteed that all the values of and are chosen uniformly at random from integers in . The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
Output
For each test case, output a single line containing an integer: the maximum number of dollars you can earn by selling diamonds.
Samples
1
4
2 3 1 5
6 3 2 4
3 5 1 4
5 2 4 1
3 2 5 1
2 4 3 5
1 2 3 4
4 3 5 3
528