Bản đồ thành phố là một bảng kích thước ~M \times 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~.

Yêu cầu:

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.

Input

• 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^5)~ cách nhau bởi 1 dấu cách.

Output

• 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~

Sample Input

5 4
4 5 2 4
3 4 5 2
3 4 5 2
5 6 3 5
4 5 2 5

Sample Output

26
2
3
3
2
2