F - 不便な橋 /

実行時間制限: 2 sec / メモリ制限: 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