問題文

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

入力例 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