No.44 玉ねぎの収穫をするkotamanegi

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

kotamanegi君は座標が(1,1)~(H,W)で表される玉ねぎ畑にいて、(y,x)にある玉ねぎを収穫したいと考えています。

玉ねぎ畑は土壌が不安定なので、畑内を移動する際に、場所によって疲れ方が違います。

kotamanegi君は一回の移動でx座標が1違う点か、y座標が1違う点に移動できます。

また、$y=i$における移動では$y_i$だけ疲れ、$x=j$における移動では$x_j$だけ疲れます。

また、畑の一部には大たまねぎ($y_l≦i≦y_r,x_l≦j≦x_r$を満たす長方形の区画に存在)があるので、その区画には移動できません 。

kotamanegi君は出来るだけ疲れたくないので、最も疲れない移動をしたときに疲労度を求めてください。

また、kotamanegi君は始め(1,1)にいます。

制約

• $2 ≦ H,W ≦ 1000$
• $1 ≦ y,x ≦ 1000$
• $1 ≦ y_i ≦ 1000$
• $0 ≦ x_i ≦ 1000$
• $1 < yl≦yr < W$
• $1 < xl≦xr < H$

入力形式

入力は以下の形式で標準入力から与えられる。

H W
y x
y_1 y_2 y_3 ... y_H
x_1 x_2 x_3 ... x_W
yl yr xl xr

出力

kotamanegi君が目的の玉ねぎを収穫するまでに蓄積する疲労度の最小値を出力してください。

但し、kotamanegi君が玉ねぎを収穫できないときは$-1$を出力してください。

入出力例

追記:テストケースを修正しました。

3 3
3 3
3 4 2
1 6 2
2 2 2 2

6

例えば、(1,1)->(2,1)->(3,1)->(3,2)->(3,3)と移動することで疲労度6で目的の玉ねぎを収穫できます。