海盜 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$ 行,每行包含 $n$ 個整數 $d_{i,j}$,表示方格 $(i,j)$ 處的水深。對於所有 $1 \le i \le m$、$1 \le j \le n$,皆有 $0 \le d_{i,j} \le 10^9$。
輸出格式
輸出能完全浸沒在池塘水面以下、尺寸皆為整數的長方體箱子的最大體積,其中頂面的一個邊長不超過 $a$,另一個不超過 $b$。如果池塘中無法藏起任何箱子,輸出 0。
範例
輸入格式 1
3 1 2 3 2 1 1 2 2 1
輸出格式 1
4
輸入格式 2
4 1 1 5 2 0 2 2 2
輸出格式 2
12
輸入格式 3
2 3 3 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
輸出格式 3
18