D - 建物

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600

問題文

kenkooooさんはSoundHound社で働いています。建物は H 階建てで、1 つのフロアは W 個の東西に直線上につながった部屋からなります。上から i 番目の階の、西から j 番目の部屋を部屋 (i,j) と呼ぶことにします。

いま、kenkooooさんは部屋 (1,1) にいます。kenkooooさんは以下の動作を繰り返すことで、地上階(上から H 番目の階)の部屋から建物を出ることにしました:

  • 部屋 (i,j) にいるとき、存在するなら部屋 (i,j-1)に移動する。
  • 部屋 (i,j) にいるとき、存在するなら部屋 (i,j+1)に移動する。
  • 部屋 (i,j) にいるとき、存在するなら部屋 (i+1,j)に移動する。

ただし、地上階にたどり着いてからも移動をしてもかまいません。

さらに、部屋 (i,j) には P_{i,j} 円が落ちており、その部屋に初めて入るときkenkooooさんはこれを拾います。

一方で、部屋 (i,j) に入るたびに、入室料として F_{i,j} 円を払う必要があります。

kenkooooさんはすでに十分大きい金額を今持っているため、途中で手持ちのお金がなくなってしまうことはありません。部屋 (H,j) から建物を出るとき、この建物で最大いくら得ることができるかをすべての 1≦j≦W について求めてください。

制約

  • 2≦H≦10
  • 1≦W≦5×10^4
  • 0≦P_{i,j}<10^5
  • 0≦F_{i,j}<10^5

入力

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

H W
P_{1,1} ... P_{1,W}
:
P_{H,1} ... P_{H,W}
F_{1,1} ... F_{1,W}
:
F_{H,1} ... F_{H,W}

出力

部屋 (H,j) から建物を出るとき、この建物で得ることのできる利益の最大値を j の昇順に出力してください。


入力例 1

2 4
2 1 3 0
0 3 0 3
0 2 0 0
5 0 5 0

出力例 1

0
5
2
7

例えば、部屋 (2,1) にたどり着くには、(1,1),(1,2),(1,3),(1,2),(2,2),(2,1) の順に訪れることで、2+1+3+3 円を手にしつつ、2+2+5 円を払うことで合計 0 円の利益を得ることができます。


入力例 2

2 4
2 0 3 5
1 3 1 3
1 3 2 1
0 0 0 10

出力例 2

6
6
6
-1

部屋 (1,1) でも入室料を取られること、地上にたどり着いた後も動いてよいこと、最終的な利益が負になることもあることに注意してください。


入力例 3

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

出力例 3

2
4
3
2