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