AT_past17_l 割引券

有 $N$ 个城市，编号为 $1$ 到 $N$。 任意两个不同的城市之间都有一条双向收费公路。你有一张代金券，可以在任意一条道路上使用该券以折扣价通过。 城市 $i$ 和城市 $j$ 之间（$i < j$）的普通通行费为 $a_{i,j}$ 日元；使用代金券后的通行费为 $b_{i,j}$ 日元（$b_{i,j} < a_{i,j}$）。 对于所有满足 $i < j$ 的城市对 $(i, j)$，求： - 从城市 $i$ 到城市 $j$，最多使用一次代金券，所需的最小总费用。

输入从标准输入读取，格式如下： > $N$ $a_{1,2}$ $a_{1,3}$ $\dots$ $a_{1,N}$ $a_{2,3}$ $\dots$ $a_{2,N}$ $\vdots$ $a_{N-1,N}$ $b_{1,2}$ $b_{1,3}$ $\dots$ $b_{1,N}$ $b_{2,3}$ $\dots$ $b_{2,N}$ $\vdots$ $b_{N-1,N}$

按以下格式输出答案。这里 $c_{i,j}$ 表示从城市 $i$ 到城市 $j$，最多使用一次代金券所需的最小费用。 > $c_{1,2}$ $c_{1,3}$ $\dots$ $c_{1,N}$ $c_{2,3}$ $\dots$ $c_{2,N}$ $\vdots$ $c_{N-1,N}$

### 样例解释 1 例如，你可以从城市 $1$ 出发，最多使用一次代金券，以总费用 $4$ 日元到达城市 $3$，具体如下： - 从城市 $1$ 到城市 $4$，使用代金券，花费 $1$ 日元。 - 然后从城市 $4$ 到城市 $3$，不使用代金券，花费 $3$ 日元。 ### 数据范围 - $2 \leq N \leq 300$ - $1 \leq b_{i,j} < a_{i,j} \leq 10^4$，其中 $i < j$ - 所有输入值均为整数。 由 ChatGPT 5 翻译