AT_tkppc4_1_f.不便な橋

sanada 君计划从岛屿 $1$ 顺次前往岛屿 $N+1$，途中需要借助桥梁进行移动。

在从岛屿 $i$ 到岛屿 $i+1$（$1 \leq i \leq N$）的路途中，有 $M$ 座桥可以选择，记为桥 $(i, j)$ 表示第 $i$ 大段上的第 $j$ 座桥。
桥 $(i, j)$ 的入口处设有一道门，该门在时间是 $A_{i, j}$ 的倍数时（包括 $0$）会开启。sanada 君必须在门开启的瞬间开始过桥，并且需要花费 $B_{i, j}$ 时间才能完全通过。
一开始，即时间 $0$，sanada 君位于岛屿 $1$。请找出 sanada 君能够到达岛屿 $N+1$ 的最早时间。

输入信息从标准输入读取，格式如下：

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

本翻译由 AI 自动生成