Giả sử có một thềm lục địa giàu dầu mỏ. Người ta chia thềm lục địa thành lưới ô vuông có M dòng và N cột (1 ≤ M ≤ 1000, 1 ≤ N ≤ 1000). Trên mỗi ô của lưới người ta ghi một số nguyên A (1 ≤ A ≤ 10^5) được gọi là trữ lượng dầu của ô đó. Để khai thác, người ta dùng một giàn khoan di động. Do kinh phí có hạn nên giàn khoan không thể chạy hết vùng có dầu được. Vì vậy, người ta qui định, nếu giàn khoan đang ở ô có tọa độ [dòng ; cột] = [x ; y] thì chỉ được phép di chuyển đến ô có tọa độ [dòng ; cột] lần lượt là [x + 1 ; y] hoặc [x ; y + 1] và khai thác tại ô có trữ lượng nhiều hơn. 

Yêu cầu: Hãy tìm đường đi (theo qui định trên) cho giàn khoan để đi từ vị trí [1 ; 1] đến vị trí [M ; N].

Dữ liệu vào: 

• Dòng đầu tiên là hai giá trị M, N cách nhau một một khoảng cách. 

• M dòng tiếp theo, mỗi dòng có N giá trị A được viết cách nhau một khoảng cách.

Dữ liệu ra:

• Dòng đầu tiên là tổng số dầu thu được sau hành trình của giàn khoan. 

• Các dòng tiếp theo, mỗi dòng là hai giá trị [dòng ; cột] viết cách nhau khoảng cách chỉ vị trí (theo thứ tự) trên lưới mà giàn khoan đã đi qua.

Ví dụ: