Cho bảng số nguyên kích thước nxm, hãy xác định tổng lớn nhất có thể của các hàng, các cột, các đường chéo phải, các đường chéo trái.

Input

Dòng đầu gồm 2 số n,m (1 ≤ n, m ≤ 1000)

Dòng thứ i (1 ≤ i ≤ n) trong n dòng sau chứa m số nguyên ~a_i, 1, a_i, 2, ..., a_i, m ( - 10^9 ≤ a_i, j ≤ 10^9)~

Output

Gồm một dòng duy nhất gồm 4 số lần lượt là tổng lớn nhất có thể của các hàng, các cột, các đường chéo phải, các đường chéo trái.

Example

Sample Input

4 5
1 2 3 100 2
1 2 3 2 -1
2 3 -100 -100 1
-1 -2 -3 -4 -5

Sample Output

108 5 99 105