Chỉ còn không lâu nữa sẽ đến ngày mà bé Đôn tròn 3 tuổi. Vì bé Đôn là một cậu bé không những hoà đồng mà còn tốt bụng nên Lê và Quý muốn tổ chức một ngày sinh nhật thật hoành tráng cho cậu, trong đó Lê đảm nhận việc mua đồ trang trí.

Khu vực bày bán đồ trang trí ở trung tâm mua sắm C giấu tên bao gồm \(n\) gian hàng, được đánh số từ \(1\) đến \(n\) theo thứ tự từ trên xuống dưới. Mỗi gian hàng có \(m\) món đồ trang trí, được đánh số từ \(1\) đến \(m\) theo thứ tự từ trái sang phải. Tuy nhiên, không phải món đồ nào cũng đẹp hay sặc sỡ giống nhau, thay vào đó món đồ thứ \(j\) ở gian hàng \(i\) sẽ có độ sặc sỡ là \(a_{ij}\). Độ sặc sỡ của một nhóm món đồ nào đấy sẽ là giá trị trung vị của nhóm này.

Hiện tại Lê đang đứng ở món đồ đầu tiên của gian hàng thứ nhất. Vì không có nhiều thời gian, Lê muốn mua hàng nhanh nhất có thể. Khi đến vị trí một món đồ nào đó, Lê sẽ lấy luôn món đồ này. Ngoài ra, Lê chỉ muốn di chuyển đi xuống hoặc sang phải và anh sẽ chỉ rời khỏi khu vực bày bán đồ trang trí này sau lấy được món đồ thứ \(m\) của gian hàng thứ \(n\). Hãy giúp Lê tìm lộ trình mua hàng sao cho độ sặc sỡ của toàn bộ số món đồ Lê mua là lớn nhất.

Ta xác định giá trị trung vị của một tập hợp số \(a_1, a_2, \ldots, a_n\) bằng cách sắp xếp tập hợp này theo thứ tự không giảm và chọn \(a_{\lfloor (n + 1)/2 \rfloor}\) là giá trị trung vị.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \leq n,m \leq 10^3\)) lần lượt là số gian hàng và số món đồ ở mỗi gian hàng.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(m\) số nguyên \(a_{ij}\) (\(0 \leq a_{ij} \leq n \times m\)) là độ sặc sỡ của món đồ thứ \(j\) của gian hàng \(i\).

Output

• Một số nguyên duy nhất là độ sặc sỡ lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n = 1\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 5
1 5 5 1 6
2 6 5 5 5
6 6 1 1 1
1 1 1 1 1

5