레이팅 미적용해적 Dick은 마침내 싸움, 약탈, 도둑질, 그리고 넓은 바다에서 많은 이들의 삶을 비참하게 만드는 일에 신물이 났다. 그래서 은퇴하기로 했고, 돈이 바닥나지 않는 한 여생을 보낼 완벽한 섬을 찾았다. 그는 지금 금화가 아주 많고, 이를 궤짝에 보관하고 싶다(어쨌든 해적이니까). Dick은 윗면이 지정된 최대 크기 이하인 정수 치수의 직사각형 궤짝을 임의의 정수 높이로 만들 수 있다. 이제 궤짝을 숨길 곳이 필요하다. 섬을 탐험하다가 그는 완벽한 해법을 찾았다. Dick은 궤짝을 탁한 연못에 가라앉혀 숨길 것이다. 연못의 수면은 직사각형이고, 높은 수직 암벽으로 둘러싸인 계곡의 바닥을 완전히 채우고 있다. Dick은 연못을 측량하여 수면 위에 놓인 직교 좌표 격자의 각 정사각형 칸에서의 깊이를 알고 있다. Dick이 궤짝을 물에 넣으면 궤짝은 바닥에 닿을 때까지 최대한 가라앉는다. 궤짝의 윗면은 연못 수면과 평행을 유지하며 궤짝은 격자 칸에 맞춰 정렬된다. 가라앉은 궤짝이 밀어낸 물은 연못 수면의 높이를 올린다(밀려난 물이 올라올 공간이 궤짝 주위에 없더라도 그렇다). 계곡의 벽은 충분히 높아서 물이 계곡 밖으로 넘칠 일은 없다. 물론 궤짝이 보이지 않아야 하므로 궤짝의 윗면은 연못 수면보다 엄격히 아래에 있어야 한다. 당신의 일은 해적 Dick이 이런 방식으로 숨길 수 있는 가장 큰 궤짝의 부피를 구하는 것이다. 그림 I.1에서 맨 왼쪽 그림은 연못을, 가운데 그림은 부피 3인 궤짝의 가능한 배치를, 맨 오른쪽 그림은 최대 부피인 부피 4인 궤짝의 배치를 보여 준다. 두 번째 궤짝을 한 단위 더 높게 만들면 윗면이 물 표면과 정확히 같은 높이가 되어 보이게 된다는 점에 유의하라. 그림 I.1: 샘플 입력 1의 그림.
입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스는 네 정수 \(a\), \(b\), \(m\), \(n\) (\(1 \le a\), b, m, \(n \le 500\))이 있는 줄로 시작한다. 연못 수면의 크기는 \(m \times n\)이고 궤짝의 윗면(과 아랫면)의 최대 크기는 \(a \times b\)이다. 또한 \(a\)와 \(b\)는 윗면 크기 \(a \times b\)인 궤짝으로 연못 전체를 덮는 것이 불가능할 만큼 작다. 테스트 케이스의 나머지 \(m\)개의 줄에는 각각 격자 칸 (i, j)에서의 연못 깊이를 나타내는 \(n\)개의 정수 \(d\)i,j가 주어지며, 각 \(1 \le i \le m\)과 \(1 \le j \le n\)에 대해 \(0 \le d\)i,\(j \le 10^{9}\)이다.
연못 수면 아래에 완전히 잠길 수 있는, 정수 치수의 직사각형 궤짝(윗면의 한 치수(dim\(en- si\)ons)는 \(a\) 이하, 다른 치수는 \(b\) 이하)의 최대 부피를 출력한다. 연못에 숨길 수 있는 궤짝이 없으면 0을 출력한다.
3 1 2 3
2 1 1
2 2 1
4
4 1 1 5
2 0 2 2 2
12
2 3 3 5
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
18