Cho một lưới ô vuông \(A\) kích thước \(m×n\), các hàng của lưới được đánh số từ \(1\) tới \(m\) từ trên xuống dưới, các cột của lưới được đánh số từ \(1\) tới \(n\) từ trái qua phải, trên mỗi ô của lưới ghi một số nguyên.
Người ta muốn tìm một cách đi từ cột \(1\) tới cột \(n\) của lưới theo quy tắc: từ một ô chỉ được phép đi sang một trong các ô ở cột bên phải có đỉnh chung với ô đang đứng (không đi ra ngoài lưới).
Hãy chỉ ra một cách đi mà tổng các số ghi trên các ô đi qua là lớn nhất.

Input

• Dòng đầu gồm 2 số nguyên dương \(m,n \leq 1000\) .
• \(m\) dòng tiếp theo, mỗi dòng là \(n\) số nguyên có giá trị tuyệt đối không vượt quá \(10^6\), số thứ \(j\) là số ghi trên ô \((i,j)\) của lưới.

Output

• Dòng 1 : Ghi tổng các số ghi trên các ô đi qua trên đường đi tìm được.
• \(n\) dòng tiếp theo mỗi dòng ghi chỉ số hàng và chỉ số cột của một ô đi qua theo đúng thứ tự trên hành trình tìm được.

Example

4 5
7 2 1 2 6
1 2 5 4 5
1 5 3 5 2
5 2 3 1 1

25
4 1
3 2
2 3
2 4
1 5