Problems
Turtle restoring
Turtle restoring
The turtle wants to pass the rectangular table as quickly as possible from top left corner to bottom right corner along the route with the least losses.
\InputFile
The first line contains two positive integers $n$ and $m~(n, m \le 1000)$ --- the size of the table. Each of the next $n$ lines contains $m$ integers --- the description of the table, each cell contains the amount of acid in it (in milliliters).
The turtle can move only one cell down or right.
\OutputFile
Print in the first line the minimal possible turtle's damage. In the next lines print the cells coordinates along which the appropriate path runs. Print the coordinates in the order like they appear on the route.
\includegraphics{https://static.e-olymp.com/content/5c/5cd94d974a6c5b3b8a5b52adcb72a55ca64ce967.gif}
Input example #1
3 4 5 9 4 3 3 1 6 9 8 6 8 12
Output example #1
35 1 1 2 1 2 2 2 3 3 3 3 4
Input example #2
1 1 1
Output example #2
1 1 1