24157번 - ショッピングモール (Mall) 다국어

クロアチアの首都ザグレブでは，IOI2007 の開催にあわせて，郊外に大型のショッピングモー ルを建設することにした．ショッピングモールの建設候補地は，下図のように横 m ブロック，縦 n ブロックの格子状に区切られている．

建設候補地の例 (m = 10, n = 7)

ザグレブ市では，建設候補地の中から横 a ブロック，縦 b ブロックの長方形の領域を選び，そ こにショッピングモールを建設することにした．しかし，建設候補地内のいくつかのブロックに は，すでに人が住んでおり，その土地にはショッピングモールを建設することができない．もし， 横 a ブロック，縦 b ブロックの長方形領域の中に人が住んでいるブロックが無ければ，その長方 形領域内のブロックを全て買収することにより，ショッピングモールを建設することができる．

ザグレブ市の財政上の理由から，用地買収にかかる費用はできるだけ少なくする必要がある． 予算案を策定するため，ショッピングモール建設のための用地買収に必要な費用を早急に計算 する必要がある．そこで，ザグレブ市では，そのためのプログラムの作成を，IOI2007 の代表 候補者であるあなたに依頼することにした．

入力として，建設候補地の大きさと，ショッピングモールの大きさが与えられ，また，各ブ ロックごとに，そこに人が住んでいるかどうかの情報と，もし人が住んでいなければそのブロッ クを買収するのに必要な費用が与えられたとき，ショッピングモール建設のための用地買収に 必要な費用の最小値を求めるプログラムを作れ．

以下では，建設候補地の左から i 列目，上から j 行目のブロックを (i, j) で表す．

入力の 1 行目には，2 つの整数 m, n (1 ≤ m, n ≤ 1000) が空白を区 切りとして書かれている．これは，建設候補地の大きさが横 m ブロック，縦 n ブロックである ことを表す．

2 行目には，2 つの整数 a, b (1 ≤ a, b ≤ 1000) が空白を区切りとして書かれている．これは， ショッピングモールの大きさが横 a ブロック，縦 b ブロックであることを表す．

続く n 行 (3 行目～n + 2 行目) には，建設候補地内の各ブロックの情報が書かれている．j + 2 行目 (1 ≤ j ≤ n) は上から j 行目のブロックの情報を表しており，m 個の整数 c_1,j , . . . , c_m,j (−1 ≤ c_i,j ≤ 100) が空白を区切りとして書かれている．c_i,j = −1 のときは，ブロック (i, j) に 人が住んでいることを表す．そうでないときは，ブロック (i, j) の買収にかかる費用が c_i,j であ ることを表す．

なお，採点に用いる入力データに対しては，ショッピングモールの建設は常に可能である．

出力は，標準出力に行うこと．ショッピングモール建設のための用地買収に必要な費 用の最小値を出力せよ．

この入出力例におけるショッピングモール建設地を図示すると，以下の通りである．×のブ ロックは，すでに人が住んでいることを意味する．