Đường đi của quân cờ

Bàn cờ là một bảng hình chữ nhật có $M \times N$ ô gồm $M$ hàng, $N$ cột. Quân cờ cần thực hiện lộ trình qua $N$ ô xuất phát phát từ một ô bất kỳ của cột 1 và kết thúc ở một ô nào đó của cột $N$. Với mỗi bước đi quân cờ chỉ được đi sang 1 ô ở cột tiếp theo trên đường chéo (hình vẽ minh họa). Trên mỗi ô chứa một số nguyên là thời gian (tính bằng phút) mà quân cờ phải lưu lại tại ô đó.

Bạn hãy giúp tìm một lộ trình để quân cờ hoàn thành với ít thời gian nhất.

Dữ liệu vào là file QuanCo.INP có cấu trúc như sau:

• Dòng đầu gồm hai số nguyên dương $M, N$ ($0 < M, N < 300$)
• $M$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên dương $A_{ij}$ là giá trị tương ứng tại ô thuộc hàng $i$, cột $j$ trong bảng ($0 < A_{ij} < 1000$).

Dữ liệu ra là file QuanCo.OUT có cấu trúc như sau:

• Dòng đầu là tổng thời gian mà quân cờ thực hiện lộ trình tốt nhất tìm được.
• $N$ dòng tiếp theo, mỗi dòng gồm hai số nguyên chỉ tọa độ của $N$ ô mà quân cờ thực hiện theo lộ trình để có kết quả tốt nhất.

• $0 < M, N < 300$; $0 < A_{ij} < 1000$.