Thành phố được mô tả dưới dạng lưới 2D kích thước N x M (1 ≤ N, M ≤ 1000). Mỗi ô (i, j) có mức độ ô nhiễm A[i][j] (0 ≤ A[i][j] ≤ 10^9). Bạn cần di chuyển từ ô (1, 1) đến ô (N, M) chỉ được phép sang phải hoặc xuống dưới.

Độ an toàn của một đường đi được định nghĩa là giá trị ô nhiễm nhỏ nhất trên đường đi đó. Hãy tìm đường đi có độ an toàn lớn nhất có thể.

Input:

Dòng 1: N và M

N dòng tiếp theo, mỗi dòng chứa M số nguyên biểu thị ma trận ô nhiễm

Output:

Một số nguyên duy nhất là độ an toàn tối đa tìm được

Input

3 3
5 4 5
1 2 5
5 2 5

Output

4

Giải thích output:

Đường đi (5 → 4 → 2 → 5) có giá trị nhỏ nhất là 2, nhưng đường đi (5 → 1 → 5 → 2 → 5) có giá trị nhỏ nhất là 1. Tuy nhiên, đường đi tối ưu là (5 → 4 → 2 → 5) với giá trị nhỏ nhất là 4.