AT_soundhound2018_d 建物

[problemUrl]: https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_d 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 $ について求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ の昇順に出力してください。

### 制約 - $ 2≦H≦10 $ - $ 1≦W≦5×10^4 $ - $ 0≦P_{i,j}\