時間制限:20000ミリ秒
メモリ制限:65536KB
各テストケースに対する時間制限:5000ミリ秒
問題
Dingilvilleに住む人々は、空港を建設するのに適した場所を探しています。その土地の地図があります。地図は単位正方形からなり、各正方形は水平位置(西東)を表すx座標と垂直座標(南北)を表すy座標の対(x,y)によって表されます。地図には各正方形における高さが記されています。
あなたの仕事は、次の条件を満たす長方形の領域のうち、最大のもの(最大の個数の正方形からなる長方形の領域)を見つけることです。
1.その領域中で最も高い正方形と最も低い正方形の高さの差が、与えられた制限C以下である。
2.その領域の幅(東西方向の辺の長さ)が100を超えない。
最大の領域はいくつかあるかもしれません。
入力
最初の行は三つの整数U,V,Cからなります。
その後のV行には整数Hxy x=1,...,Uが書かれています。すなわち,Hxyは、(V-y+2)行目のx番目の整数です。
1<=U<=700,1<=V<=700 ここでU,Vは地図の寸法です。詳しく言うと、Uは東西方向の正方形の数で、Vは南北方向の正方形の数です。
0<=C<=10
-30000<=Hxy<=30000 Hxyは座標(x,y)の正方形の高さです。南西の角の座標は(1,1)で、北東の角の座標は(U,V)です。
出力
最大の領域の面積を出力してください。
入力の例
10 15 4 41 40 41 38 39 39 40 42 40 40 39 40 43 40 36 37 35 39 42 42 44 41 39 40 38 40 41 38 35 37 38 38 33 39 36 37 32 36 38 40 39 40 39 39 39 40 40 41 43 41 39 40 41 38 39 38 39 39 39 42 36 39 39 39 39 40 39 41 40 41 31 37 36 41 41 40 39 41 40 40 40 40 40 42 41 40 39 39 39 39 42 40 44 40 38 40 39 39 37 41 41 41 40 39 39 40 41 40 39 40 47 45 49 43 43 41 41 40 39 42 42 41 41 39 40 39 42 40 42 42 41 44 49 43 46 41 42 41 42 42 45 40 42 42 46 42 44 40 42 41
出力の例
35
出典
IOI 1999