Bản đồ một trang trại là một hình chữ nhật kích thước m×n được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ 1 tới ~m~ từ trên xuống dưới và các cột của lưới được đánh số từ ~1~ tới ~n~ từ trái qua phải. Ô nằm trên giao của hàng ~x~, cột ~y~ được gọi là ô ~(x,y)~ và ô đó có độ cao là ~h_{xy}~.
Trong những ngày mưa tầm tã, mực nước dâng lên và trang trại bị ngập dần trong nước. Nếu mực nước là ~k~ thì những ô có độ cao ~≤ k~ được coi là ngập nước còn những ô có độ cao ~> k~ được coi là chưa ngập nước. Những ô chưa ngập nước tạo thành những "đảo" định nghĩa như sau: Hai ô chưa ngập nước được gọi là cùng đảo nếu ta có thể đi từ ô này tới ô kia bằng cách di chuyển qua các ô kề cạnh chưa ngập nước, ngược lại hai ô đó được coi là nằm trên hai đảo khác nhau. Ví dụ với bản đồ dưới đây, ta có 4 đảo khi mực nước bằng 2, có 2 đảo khi mực nước bằng 7
Yêu cầu: Giả sử trong những ngày mưa, mực nước dâng dần lên cho tới khi toàn bộ các ô đều ngập nước, xác định số đảo tại một thời điểm trong những ngày mưa mà tại thời điểm đó có nhiều đảo nhất.
Dữ liệu:
- Dòng 1 chứa hai số nguyên dương ~m,n~ ≤ ~1000~
- ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên dương, số thứ ~j~ là ~h_{ij}~≤ ~10^6~.
Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra một số nguyên duy nhất là số đảo tại thời điểm có nhiều đảo nhất.
Ví dụ
INPUT
6 6
9 1 8 1 5 4
7 1 8 1 5 5
7 7 8 1 1 1
1 1 1 1 6 6
3 3 1 6 6 1
3 3 1 6 1 1
OUTPUT
4
Comments