Mutants-2
At the Institute of Arts, Mutants, and Information Technology, they breed adorable multicolored creatures. However, one day, one of these creatures managed to escape and found its way to the remarkable city of Mutantograd. Interestingly, the city is organized into streets with intersections at each crossroad.
Mutantograd is unique in that movement is restricted to traveling from intersection to intersection either eastward or southward, and each intersection imposes a fine. The creature discovered a city map, represented as an N by M grid, where each cell at the i-th row and j-th column specifies the fine for landing on that intersection.
The creature starts at the northwestern corner of the city. Your task is to help it reach the southeastern corner while incurring the smallest possible fine.
Input
The first line of the input contains two natural numbers N and M (1 ≤ N, M ≤ 1000).
The next N lines contain M numbers each, representing the map of Mutantograd.
Output
On the first line, output a single integer representing the minimum fine the creature must pay.
On the second line, output the number of intersections on the path.
In the subsequent lines, list the coordinates of the intersections the creature will traverse. It is guaranteed that the fine will not exceed 10^9.