You have a grid with n rows and m columns. Cell at the -th row and the -th column is called and id of the cell is . Each cell has a unique id from 1 to n,m. You can jump from to by consuming power . In each day, you are going to select a number . In that day, you can jump cells, meaning if you are currently in a cell with id number , then in one jump, you can go to another cell which id is . In the second jump you will be in , then and so on. At -th day, you have to go from -th cell to -th cell. You can select different D for each day. Now, you want to minimize the total power consumption.
Input starts with two integers and ().
Each of the next n lines contain integers representing the grid. Then the next line contains one integer (), representing the number of days. The next lines will have the information of each day. In each line, there will be two id and ().
For each day, you have to output minimum power on a line by itself.
Input | Output |
---|---|
3 3 1 4 3 2 5 7 8 9 6 4 4 8 6 9 5 8 1 9 | 9 3 6 12 |
In the last day, you want to go from 1st cell to 9th. You can select 1, 2, 4, 8 as the candidate values for D for that day. Otherwise you can not go from 1st cell to 9th cell. If you select 1 as D, you have to go through 1, 2, 3, 4, 5, 6, 7, 8, 9. The cost will be If you select 2 as D, you have to go through 1, 3, 5, 7, 9. The cost will be . If you select 4 as D, you have to go through 1,5,9. The cost will be . If you select 8 as D, you have to go through 1,9. The cost will be So, the minimum cost will be 12. |