AT_soundhound2018_d 建物

kenkoooo 先生在 SoundHound 公司工作。现在公司的大楼有 $H$ 层，每一层都有 $W$ 个房间，房间从东到西一列直排。我们称第 $i$ 层自西向东第 $j$ 个房间为房间 $(i, j)$。 现在，kenkoooo 先生位于 $(1,1)$ 房间。他可以依次进行以下动作，最终从地面层（即自上而下第 $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 先生手头有足够多的钱，不必担心途中资金短缺。请对于所有 $1 \leq j \leq W$，求出从 $(H, j)$ 房间离开时，在这座大楼中能够获得的最大利润。

输入的格式如下，通过标准输入给出。 > $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}$

请按 $j$ 的升序输出从 $(H, j)$ 房间离开时所能获得的最大利润。

### 数据范围 - $2 \leq H \leq 10$ - $1 \leq W \leq 5 \times 10^4$ - $0 \leq P_{i,j}