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 ≤ 15, 1 ≤ N ≤ 15). Trên mỗi ô của lưới người ta ghi một số nguyên A (1 ≤ A ≤ 1000) đượ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].

Yêu cầu: Viết chương trình sử dụng đệ quy quay lui để tìm đường đi (theo qui định trên) cho giàn khoan để đi từ vị trí [1 ; 1] đến vị trí [M ; N] và khai tác được lượng dầu nhiều nhất.

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.

Dữ liệu input đảm bảo tồn tại duy nhất 1 đường đi.

Ví dụ: