Problem Description

Kenkoooo works at SoundHound Inc. The building has $ H $ floors, and each floor consists of $ W $ rooms connected in a straight line from west to east. Let's call the room located on the $ i $-th floor from the top and the $ j $-th room from the west room $ (i,j) $.

Currently, Kenkoooo is in room $ (1,1) $. Kenkoooo decided to leave the building by repeating the following actions:

• When in room $ (i,j) $, move to room $ (i,j-1) $ if it exists.
• When in room $ (i,j) $, move to room $ (i,j+1) $ if it exists.
• When in room $ (i,j) $, move to room $ (i+1,j) $ if it exists.

Note that moving after reaching the ground floor (the $ H $-th floor) is allowed.

Additionally, room $ (i,j) $ contains $ P_{i,j} $ yen, which Kenkoooo picks up the first time he enters the room.

On the other hand, each time Kenkoooo enters room $ (i,j) $, he has to pay an entrance fee of $ F_{i,j} $ yen.

Kenkoooo already has a sufficiently large amount of money, so he will never run out of money during the process. For each $1 \leq j \leq W$, determine the maximum amount of money Kenkoooo can gain when leaving the building from room $ (H,j) $.

Input Format

The input is given from the standard input in the following format:

$ 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} $

Output Format

Output the maximum profit Kenkoooo can gain when leaving the building from room $ (H,j) $ in ascending order of $ j $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
5
2
7

Sample Input #2

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

Sample Output #2

6
6
6
-1

Sample Input #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

Sample Output #3

2
4
3
2

Notes/Hints

Constraints

• $2 \leq H \leq 10$
• $1 \leq W \leq 5 \times 10^4$
• $0 \leq P_{i,j} < 10^5$
• $0 \leq F_{i,j} < 10^5$

Sample Explanation 1

For example, to reach room $ (2,1) $, visiting in the order of $ (1,1),(1,2),(1,3),(1,2),(2,2),(2,1) $ allows Kenkoooo to collect $ 2+1+3+3 $ yen while paying $ 2+2+5 $ yen, resulting in a total profit of $ 0 $ yen.

Sample Explanation 2

Note that the entrance fee is also charged at room $ (1,1) $, moving after reaching the ground floor is allowed, and the final profit can be negative.

见题面 Input 部分

见题面 Output 部分