Kiến đi đến góc đối diện

Sân trường là một lưới \(M\) hàng, \(N\) cột. Ô \((i, j)\) ở hàng \(i\) (đếm từ trên xuống) và cột \(j\) (đếm từ trái sang) chứa \(a_{i,j}\) đơn vị thức ăn; giá trị âm nghĩa là kiến bị mất thức ăn khi bước vào ô đó.

Chú kiến xuất phát từ ô \((1,1)\) và muốn đến ô \((M,N)\). Mỗi bước, kiến chỉ được sang ô bên phải \((i, j+1)\) hoặc ô bên dưới \((i+1, j)\). Tổng thức ăn là tổng các giá trị trên mọi ô đi qua, kể cả ô đầu và ô cuối.

Hãy tìm tổng lớn nhất và in ra một đường đi đạt tổng đó. Để đáp án duy nhất, nếu có nhiều đường đi cùng đạt tổng lớn nhất, hãy in đường đi ưu tiên đi xuống trước: tại mỗi vị trí, nếu bước xuống ô bên dưới vẫn còn có thể hoàn thành một đường đi tối ưu thì bắt buộc phải bước xuống, chỉ khi không được mới sang phải. (Tương đương: xâu các bước 'D' (xuống) và 'R' (phải) nhỏ nhất theo thứ tự từ điển với 'D' < 'R'.)

Input

• Dòng đầu chứa hai số nguyên \(M\) và \(N\).
• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên \(a_{i,1}, \dots, a_{i,N}\).

Output

• Dòng đầu tiên: tổng lớn nhất.
• Dòng thứ hai: số ô trên đường đi, luôn bằng \(M + N - 1\).
• Mỗi dòng trong \(M + N - 1\) dòng tiếp theo chứa hai số \(i\ j\) là toạ độ một ô trên đường đi, theo thứ tự từ ô \((1,1)\) đến ô \((M,N)\).

Constraints

• \(1 \le M, N \le 1000\)
• \(|a_{i,j}| \le 10^9\)

Sample Input

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

Sample Output

28
6
1 1
2 1
2 2
3 2
3 3
3 4

Explanation

Đường đi \((1,1) \to (2,1) \to (2,2) \to (3,2) \to (3,3) \to (3,4)\) cho tổng \(5 + 3 + 6 + 2 + 9 + 3 = 28\), là lớn nhất.