Problem: dp1
You are an explorer walking through an ancient ruined cave and you're being followed by lava! Fortunately, it's moving fairly slowly, so you have time to write code before it catches up to you. Up ahead is a rectangular room (of up to 16m×16m), divided into a grid of 1m×1m squares. Inside each square is a treasure chest. Unfortunately, because the lava is following you, you will not have time to open every chest and get all the treasure. In fact, once you enter through the door (in the north-west corner), you can open each chest you come across, but you can only walk east or south at each step: if you try to walk north or west, the lava will catch you! You need to walk through the room ending at the south-east corner, where you find the door to leave the room. Of course, you want to get as rich as possible by opening the treasure chests; to help you, you have a map of the room showing how much money the treasure in each chest is worth.
Input
The input will consist of a sequence of test cases. Each test case consists of two integers r and c (the dimensions of the room, in rows and columns), followed by rc integers representing the values of the items in the chests. The numbers are in row-major order, starting in the north-west corner, proceeding east, then moving south at the end of each row.
Bounds
There are around 1000 test cases. Each test case has 1 ≤ r,c ≤ 16. The value of the item in each chest is between 0 and 1999, inclusive.
Output
For each test case, output a line. For the line, output, separated by a single space each, a sequence of integers. The first integer should be the total value of the items to collect. Following this should be the coordinates of the rooms to visit, in order; each coordinate should be reprented as a pair of integers, row followed by column. Clearly, the first two numbers should be zeroes, and the last two numbers should be r−1 and c−1 in that order.
There are multiple correct answers for some possible inputs. Any path that gives the optimal value will be accepted.
Sample Input
4 3 777 915 1793 335 1386 492 649 1421 362 27 690 59 4 3 540 1426 1172 1736 1211 1368 567 429 1782 1530 862 1123 4 4 1929 1802 22 1058 1069 167 1393 456 1011 42 229 1373 421 919 1784 537
Sample Output
5248 0 0 0 1 1 1 2 1 3 1 3 2 7760 0 0 1 0 1 1 1 2 2 2 3 2 7841 0 0 0 1 1 1 1 2 2 2 3 2 3 3