Traffic Rules at LKS#4052
Kolya, a ninth-grader, recently joined the Summer Cinematography School and decided to visit the film studio first. The school is held at the "Orlyatko" children's camp, which features numerous paved paths intersecting at crossroads. This camp is unique because all paths and intersections are marked, and traffic rules apply, with fines for any violations.
The film studio is located southeast of Kolya's residence, so he plans to travel only east and south. Eager to reach the studio quickly, Kolya intends to disregard the rules and cross intersections freely. However, as a diligent SCS student, he wants to minimize the total fines incurred from his violations. Your task is to help him achieve this.
You are provided with a map of the camp, represented as an N \times M grid. Each intersection at the -th row and -th column indicates the fine for crossing it. All indices in the grid are 1-based (1 \leq i \leq N, 1 \leq j \leq M).
Kolya's residence is at the northwest corner of the camp, and the film studio is at the southeast corner. Your goal is to find the path that allows Kolya to reach the studio while incurring the minimum possible fine.
The first line of the input contains two natural numbers and (1 \leq N, M \leq 1000), the number of rows and columns in the grid.
The next lines each contain numbers, representing the fines for each intersection in the corresponding row of the "Orlyatko" camp.
On the first line, output a single integer representing the minimum fine Kolya will have to pay. On the second line, output the number of intersections on the path. In the subsequent lines, output the coordinates of the intersections Kolya will pass through in order, from start to finish (N, M). Each line should contain two integers: and (1 \leq i \leq N, 1 \leq j \leq M) of an intersection.
It is guaranteed that the total fine will not exceed 10^9.
Example 1