Minh đang sắp đón chào một chú hải cẩu mới về trạm nghiên cứu tại cực Bắc của mình, nơi mà cậu sẽ phải đưa nó đi qua các khu trong trạm để tới nơi ở mới của nó. Tại trạm của cậu, cơ sở vật chất đã cũ mà bầy hải cẩu con nào con nấy lại đều to béo, nên cậu khá lo khi việc đưa thêm một bé nặng trĩu đi ngang qua nữa có thể khiến lớp băng dưới khu đó nứt ra!

Cụ thể hơn, trạm của Minh gồm các khu xếp thành một bảng ~M \cdot N~ đánh số từ 1 theo thứ tự từ trên xuống và từ trái qua, khu ở hàng ~i~ cột ~j~ có thể chịu thêm sức nặng tối đa là ~A_{i, j}~. Cậu cần đưa nó đến khu ~(M, N)~ từ cổng vào trạm ở vị trí ~(1, 1)~, ở mỗi khu cậu có thể qua các khu kề cạnh khu hiện tại. Liệu chú hải cẩu này có thể có cân nặng tối đa là bao nhiêu để Minh có thể đưa nó an toàn đến khu của nó?

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~M~, ~N~ cho biết độ lớn của trạm nghiên cứu. (~1 \leq M, N \leq 10^3~).
• ~M~ dòng tiếp theo, mỗi dòng ghi ~N~ số nguyên dương là sức chịu của từng khu (~1 \leq A_{i, j} \leq 10^9~).

Output

Ghi ra một số duy nhất cho biết cân nặng tối đa của chú hải cẩu mà Minh có thể mang theo.

Sample input

3 3
1 2 3
4 5 6
7 8 9

Sample output

1

Subtask

• ~30\%~ số test có ~1 \leq M, N \leq 3~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.