F - 不便な橋 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300 点

問題文

sanada君は島 1 から島 N+1 まで順に橋を使って移動します。
島 i から島 i+1 (1 \leq i \leq N) へは M 本の橋がかけられており、そのうち j 本目の橋を橋 (i, j) とします。
橋 (i, j) の島 i 側の入り口にはゲートがあり、橋 (i, j) のゲートは時刻が A_{i, j} の倍数（0も含む）である瞬間にだけ開きます。
sanada君はこの瞬間にのみ橋を渡り始めることができ、渡り切るのには B_{i, j} の時間がかかります。
時刻 0 にsanada君は島 1 にいます。sanada君が島 N+1 に到着できる最も早い時刻を出力してください。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 500
  • 1 \leq M \leq 500
  • 1 \leq A_{(i,j)} \leq 10^5
  • 1 \leq B_{(i,j)} \leq 10^5

入力

入力は以下の形式で標準入力から与えられます。

N　M
A_{(1,1)}　A_{(1,2)}　\ldots　A_{(1,M)}
A_{(2,1)}　A_{(2,2)}　\ldots　A_{(2,M)}
\vdots
A_{(N,1)}　A_{(N,2)}　\ldots　A_{(N,M)}
B_{(1,1)}　B_{(1,2)}　\ldots　B_{(1,M)}
B_{(2,1)}　B_{(2,2)}　\ldots　B_{(2,M)}
\vdots
B_{(N,1)}　B_{(N,2)}　\ldots　B_{(N,M)}

出力

sanada 君が島 N+1 に到着できる最も早い時刻を 1 行に出力してください。

入力例1

3 3
2 5 1
1 3 2
5 7 4
3 3 4
5 1 4
4 6 2

出力例1

6

以下のような動きが最適となります。この場合、時刻 6 に目的地の島 4 に到着することができます。

  • 橋 (1, 1) を時刻 0 に渡り始める。渡り切るのに 3 の時間がかかる。
  • 時刻 3 に島 2 に到着する。
  • 橋 (2, 2) を時刻 3 に渡り始める。渡り切るのに 1 の時間がかかる。
  • 時刻 4 に島 3 に到着する。
  • 橋 (3, 3) を時刻 4 に渡り始める。渡り切るのに 2 の時間がかかる。
  • 時刻 6 に島 4 に到着する。

writer: iwaiwaiwa