---
# System prepended metadata

title: Turtle With Answer

---

# 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 ﬁnishes the path in the rightmost bottom cell. Let’s calculate the sum of all numbers on visited cells (including the starting and the ﬁnishing cells). Find the minimal possible value of this sum and the way how this minimum can be achieved.

## Input format
The ﬁrst 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 ﬁrst 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 ﬁrst by the turtle move from the former one. The ﬁrst 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
```

