Trên bàn cờ tổng quát kích thước ~m~×~n~ người ta ghi vào mỗi ô ~(i,j)~ một số nguyên ~a_{ij}~. Hãy tìm cách đặt một quân hậu vào đúng 1 ô trên bàn cờ sao cho tổng các số ghi trên các ô bị quân hậu đó khống chế là lớn nhất. (Quân hậu không chế tất cả các ô trên cùng hàng, cùng cột hoặc cùng đường chéo, tính cả ô nó đang đứng)

Dữ liệu:

• Dòng 1 chứa hai số nguyên ~m,n~ (~1≤m,n≤1000~)
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên, số thứ ~j~ là ~a_{ij}~ (~|a_{ij} |≤10^6~)

Kết quả:

Ghi ra một số nguyên duy nhất là tổng các số ghi trên các ô bị quân hậu khống chế theo phương án đặt hậu tìm được

Input

4 4
1 1 2 2
3 3 4 4
5 5 6 6
7 7 8 8

Output

59