Bản đồ thành phố là một bảng kích thước M x N, các cột được đánh chỉ số từ trái sang phải, các dòng được đánh chỉ số từ trên xuống dưới. Hiện nay thành phố đang bị ô nhiễm nặng, trên mỗi ô (i,j) (giao nhau bởi dòng i và cột j) có A[i][j] đơn vị rác thải.

Thị trưởng thành phố quyết định sử dụng một con robot đi thu gom rác ở các ô. Robot được lập trình chỉ đi theo hướng xuống dưới, tức là từ ô (i,j) robot chỉ có thể đi tới ô (i+1,j-1), (i+1,j) hoặc (i+1,j+1). Chính vì vậy để robot có thể thu gom được nhiều rác nhất thì người ta phải cho robot xuất phát từ dòng 1 và đi xuống dòng M.

Hãy xác định vị trí cột xuất phát tại dòng 1 và hành trình của robot sao cho robot có thể thu gom được nhiều rác thải nhất.

Dữ liệu vào:

- Dòng đầu chứa hai số M và N (1 <= M, N <= 1000).
- M dòng tiếp theo mỗi dòng ghi N số nguyên A[i,j] (0 <= A[i,j] <= 10⁵) cách nhau bởi 1 dấu cách.

Kết quả ra:

- Dòng đầu là số lượng rác thải lớn nhất thu được
- Dòng thứ 2 ghi số k là cột mà robot sẽ xuất phát tại dòng 1.
- Dòng thứ i + 2 ghi số L là cột mà robot sẽ đi trên hành trình từ dòng 2 tới dòng M