Time Limit: 1s
Memory Limit: 128MB
삼통치킨 양계장에 때 아닌 태풍이 몰아쳐 홍수가 났고, 닭들은 정신적 충격을 받고 물에 대한 트라우마를 갖고 매일 같이 말라가고 있다.
하지만 좋은 보험을 들지 않았기 때문에 딱 한 지역에 대해서만 원래 땅으로 복구받을 수 있다.
아무래도 침수된 지역의 넓이가 가장 큰 곳을 복구받는 것이 이득일 것이다. 침수된 구역이 복구된다면 닭들은 물에 대한 트라우마를 이겨내고 무사히 기름속으로 뛰어들 수 있게될 것이다! Halleluja! 이번 기회에 삼통치킨 4호점이 오픈할 수 있도록 도와주자.
농장은 가로 M, 세로 N의 직사각형 격자로 이루어져있다.
각 칸은 멀쩡하거나 물에 잠겨있고, 정확히 K칸이 물에 잠겨있다.
변을 공유하는 물에 잠겨있는 칸들이 합쳐져서 거대한 호수를 이룰 수 있다.
* 줄 1 : 정수 N, M, K (1 ≤ N,M ≤ 100, 1 ≤ K ≤ NxM)
* 줄 2 ~ K +1 : 물에 잠겨있는 칸의 위치 R, C ( 1 ≤ R ≤ N, 1 ≤ C ≤ M)
* 줄 1 : 가장 큰 호수의 크기
3 4 5 3 2 2 2 3 1 2 3 1 1
4
USACO 2007 November Bronze