2007-day1-mall-prob

ショッピングモール (Mall)

時間制限 : 6sec / スタック制限 : 64MB / メモリ制限 : 64MB

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

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

　ザグレブ市では，建設候補地の中から横a ブロック，縦b ブロックの長方形の領域を選び，そこにショッピングモールを建設することにした．しかし，建設候補地内のいくつかのブロックには，すでに人が住んでおり，その土地にはショッピングモールを建設することができない．もし，横a ブロック，縦b ブロックの長方形領域の中に人が住んでいるブロックが無ければ，その長方形領域内のブロックを全て買収することにより，ショッピングモールを建設することができる.
　ザグレブ市の財政上の理由から，用地買収にかかる費用はできるだけ少なくする必要がある．予算案を策定するため，ショッピングモール建設のための用地買収に必要な費用を早急に計算する必要がある．そこで，ザグレブ市では，そのためのプログラムの作成を，IOI2007 の代表候補者であるあなたに依頼することにした．
　入力として，建設候補地の大きさと，ショッピングモールの大きさが与えられ，また，各ブロックごとに，そこに人が住んでいるかどうかの情報と，もし人が住んでいなければそのブロックを買収するのに必要な費用が与えられたとき，ショッピングモール建設のための用地買収に必要な費用の最小値を求めるプログラムを作れ．
　以下では，建設候補地の左からi 列目，上からj 行目のブロックを(i, j) で表す．

入力

　入力ファイルmall.in の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 であることを表す．
　なお，採点に用いる入力データに対しては，ショッピングモールの建設は常に可能である．

出力

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

入出力例

入力例1	出力例1
`7 6 3 2 26 29 84 15 -1 1 71 45 14 38 91 62 77 35 68 -1 -1 90 63 56 70 31 2 4 74 72 41 90 100 26 21 -1 44 72 60 71 4 40 93 48 -1 50`	`184`