Mê cung tối đa

Trong một buổi học toán ở trường tiểu học, FullHouse Dev được cô giáo giao cho một bài toán thú vị để rèn luyện tư duy logic. Bài toán liên quan đến việc tìm giá trị tối đa trong một ma trận với các điều kiện đặc biệt. Với tinh thần ham học hỏi, FullHouse Dev đã bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một ma trận 2 chiều có kích thước \(N \times M\), các phần tử của ma trận là số nguyên. Các hàng của ma trận được đánh số từ trên xuống dưới từ \(1\) đến \(N\), các cột được đánh số từ trái sang phải từ \(1\) đến \(M\). Phần tử nằm ở giao điểm của hàng thứ \(i\) và cột thứ \(j\) được ký hiệu là \(a_{ij}\).

Nhiệm vụ của FullHouse Dev là tìm giá trị tối đa có thể của \(K\), sao cho:

Tồn tại ít nhất một hàng và một cột mà tất cả các phần tử trong hàng và cột đó đều \(\geq K\).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách - số hàng và số cột của ma trận.
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên cách nhau bởi dấu cách, biểu diễn ma trận.

OUTPUT FORMAT:

• In ra giá trị của \(K\).

Ràng buộc:

• \(1 \leq N, M \leq 1000\)
• \(1 \leq a_{ij} \leq 10^9\)

Ví dụ

INPUT

3 3
2 1 3
4 2 4
5 9 6

OUTPUT

3

Giải thích

Nếu \(K = 3\), tất cả các phần tử trong hàng 3 và cột 3 đều thỏa mãn điều kiện \(\geq K\). Có thể chứng minh rằng \(K\) không thể lớn hơn 3.

FullHouse Dev đã giải quyết bài toán này một cách xuất sắc, khiến cô giáo rất ấn tượng với khả năng tư duy logic của em. Cô nhận xét rằng việc giải các bài toán như thế này không chỉ giúp các em phát triển kỹ năng toán học mà còn rèn luyện tư duy phân tích và giải quyết vấn đề, rất hữu ích cho tương lai.