# Turtle With Answer

# Turtle

There is an $N \times M$ rectangular grid. The turtle is in the leftmost top corner. Each cell of the grid contains a number. The turtle can make moves of three types:
* 1 step down,
* 1 step to the right or
* 1 step to the down-right diagonal direction in a single move.

The turtle finishes the path in the rightmost bottom cell. Let’s calculate the sum of all numbers on visited cells (including the starting and the finishing cells). Find the minimal possible value of this sum and the way how this minimum can be achieved.

## Input format
The first line contains two integer positive numbers $N, M (1 \le N, M \le 1,000)$. The following $N$ lines contain the description of the grid. Each of these lines contains $M$ integers — numbers in the grid cells. All those integers are between $−1,000$ and $1,000$, inclusive.

## Output format
In the first line print two integers — the minimum sum and the number $q$ of cells in your path.
Then print $q$ lines, each line containing two integers — 1-based numbers of the row and the column of the next visited cell. For each two consecutive cells the later one has to be reachable from first by the turtle move from the former one. The first cell should be the leftmost top, the last cell should be the rightmost bottom. If there is more than one way with a minimal sum, print any of them.

### Sample 1

#### Input

4 4
1 3 5 2
-1 4 2 9
5 -6 1 -4
-6 6 -2 2

#### Output

-7 6
1 1
2 1
3 2
3 3
3 4
4 4

### Sample 2

#### Input

2 4
1 2 3 4
5 6 7 8

#### Output

14 4
1 1
1 2
1 3
2 4