← 返回题目列表

AtCoder · soundhound2018_d

D. 建物

中文机器翻译题面 查看原题

配点 : 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