問題
あなたは、都市NOW_MAN_ZAWにやってきた。
この都市は、 H 行 W 列のマスに区切られた長方形の形をしている。
それぞれの区画にはビルが建ち並んでおり、それぞれ高さが異なる。それぞれの区画には必ずビルがある。
さて、都市NOW_MAN_ZAWでまた騒動が起こっていますね。みてみましょう。
市民No 114 「隣のビルでかスギィ！ せめてわれわれの会社のビルの大きさくらいにしてもらいたいものですよ、まったく。」
それを聞いた狂ったこの都市の市長。
「その付近の地域のビルの高さを全て同じにするためにビルを削ってやるのです。われわれはかしこいので。」
「フハハハハ！ウワァーーーーーー！！！！」
と、言い出した。
ということで市長はビルの高さを合わせるために、
指定された範囲の区画のビルの高さが全て同じになるようにビルを削ろうとした。
1mビルを削ると、そのビルの高さは1mだけ下がる。
削るには当然コストが必要だ。1mビルを削るには、コストCがかかる。
そこで、市長はあなたに頼みました。
「今からビルの高さを同じにしたい範囲をたくさん言ってやるので、
それぞれ削るコストがどのくらいになるか見積もるのです。」
「フハハハハ！ウワァーーーーーー！！！！」
課題
都市の大きさ、市長が見積もりを要求する数、1mビルを削るために必要なコスト、ビルの高さの情報が与えられるので、
ビルの高さを同じにする範囲が与えられたとき、ビルを適切に削ることでかかるコストを求めよ。
与えられる要求は、「もしも削った場合コストがどのくらいかかるか」なため、実際にビルを削っているわけではない。
つまり、以前の要求によってビルが削られている状態で要求を受けるわけではない。
なお、ビルの高さを上げることは不可能である。
入力
1行目に都市の行の数 H , 列の数 W ,
市長が見積もりを要求する数 Q , 1mビルを削るために必要なコスト C が与えられる。
2行目から 1 + H 行目まで、
それぞれの区画のビルの高さmi j[m] ( 1 ≦ i ≦ H , 1 ≦ j ≦ W )が与えられる。
2 + H行目から1 + H + Q 行目まで、
ビルの高さを同じにしたい範囲
始点 x1k, y1k,
終点 x2k, y2k
( 1 ≦ k ≦ Q )が与えられる。
始点から終点で囲まれる長方形が、ビルの高さを同じにしたい範囲である。
x1kから x2kまでの列を含み、かつ、
y1kから y1kまでの行を含むといえる。
H W Q C
m1 1 m1 2 ...... m1 W
m2 1 m2 2 ...... m2 W
.
.
.
mH 1 mH 2 ...... mH W
x11 y11 x21 y21
x12 y12 x22 y22
.
.
.
x1Q y1Q x2Q y2Q
出力
それぞれの要求に対して、ビルを削ることでかかるコストを求め、出力せよ。
要求は Q 行与えられるので、 Q 行だけ出力する。
制約
- 1 ≦ H , W ≦ 20
- 1 ≦ Q , C ≦ 100
- 1 ≦ mi j ≦ 100
- 1 ≦ x1k ≦ x2k ≦ W かつ、1 ≦ y1k ≦ y2k ≦ H
入出力例
入力例1
3 3 2 3 53 32 11 19 50 19 20 10 19 2 2 3 3 1 1 3 2
出力例1
174 354
解説
1個目の要求で一番小さいビルは、50, 19, 10, 19の中の10であるため、三つのビルを高さ10[m]まで削る場合、
(50 - 10) × 3 + (19 - 10) × 3 + (19 - 10) × 3より、174という結果となる。
入力例2
6 7 4 9 40 12 45 23 12 89 43 11 15 14 8 10 19 19 36 43 64 10 10 90 89 100 21 1 50 23 53 12 90 10 23 53 23 53 99 46 69 38 49 28 37 49 3 3 4 5 1 2 7 6 3 4 4 5 1 1 7 6
出力例2
1755 11970 1107 14283
コメント
けものフレンズ要素がいっぱいなのだ
市長は(アライさん+博士) / 2です。
しかし、オグロプレーリードッグについては要素が入っているのかわからなくなったので
生 き 埋 め に し て や ら れ た で あ り ま す ！ ！ ！