Dũng sĩ Mofk đang trên con đường hành đạo của mình. Một ngày nọ, anh tới một khu vực với kích thước ~n*m~, con quái vật trên ô ~(i,j)~ có sức mạnh ~h_{i,j}~.

Nếu đang có sức mạnh ~s~, dũng sĩ Mofk có thể tiêu diệt các con quái vật có sức mạnh ~x~ thỏa mãn ~x < s~. Sau khi tiêu diệt con quái vật này, Mofk có thể đi vào ô chứa quái vật đó, đồng thời sức mạnh của anh sẽ cộng thêm ~x~. Ngược lại, nếu không thể tiêu diệt quái vật, anh sẽ không thể đi vào ô chứa nó.

Hãy tính sức mạnh nhỏ nhất ban đầu của dũng sĩ Mofk để anh có thể xuất phát từ ô ~(1,1)~, chỉ đi sang phải hoặc xuống dưới và đến được ô ~(n,m)~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ ~(1 \le n,m \le 1000)~.

• Từ dòng ~2~ tới ~n+1~, mỗi dòng gồm ~m~ số nguyên dương mô tả bảng ~h_{i,j}~ ~(1 \le h_{i,j} \le 10^9)~.

Output

• Gồm một dòng in ra sức mạnh ~s~ nhỏ nhất ban đầu của dũng sĩ Mofk để thỏa mãn yêu cầu đề bài.

Scoring

• Có ~20\%~ số test thỏa mãn ~n = 1~.

• Có ~30\%~ số test thỏa mãn ~1 \le n,m \le 100~ và đáp án luôn không vượt quá ~100~.

• Có ~50\%~ số test không có ràng buộc gì thêm.

Sample Input 1

2 2
1 2
3 4

Sample Output 1

2

Notes

Ban đầu dũng sĩ Mofk có sức mạnh là ~2~.

Khi đi đến ô ~(1, 1)~, dũng sĩ tiêu diệt con quái vật ở đây và sức mạnh trở thành ~3~.

Khi đi đến ô ~(1, 2)~, dũng sĩ tiêu diệt con quái vật ở đây và sức mạnh trở thành ~5~.

Khi đi đến ô ~(2, 2)~, dũng sĩ tiêu diệt con quái vật ở đây và sức mạnh trở thành ~9~.