AT_abc325_e [ABC325E] Our clients, please wait a moment

某国有 $N$ 个城市。 你打算从城市 $1$ 的营业所出发，经过 $0$ 个或多个城市，前往城市 $N$ 的访问地点。 你可以选择两种交通方式：公司用车和电车。从城市 $i$ 到城市 $j$ 的所需时间如下： - 使用公司用车时：$D_{i,j} \times A$ 分钟 - 使用电车时：$D_{i,j} \times B + C$ 分钟 但是，你可以从公司用车换乘到电车，但不能从电车换回公司用车。 此外，换乘只能在各个城市进行，且换乘不需要时间。 从城市 $1$ 到城市 $N$ 的最短所需时间是多少分钟？

输入按以下格式从标准输入给出。 > $N$ $A$ $B$ $C$ $D_{1,1}$ $D_{1,2}$ $\ldots$ $D_{1,N}$ $D_{2,1}$ $D_{2,2}$ $\ldots$ $D_{2,N}$ $\vdots$ $D_{N,1}$ $D_{N,2}$ $\ldots$ $D_{N,N}$

请输出答案的整数值。

### 限制条件 - $2 \leq N \leq 1000$ - $1 \leq A, B, C \leq 10^6$ - $D_{i,j} \leq 10^6$ - $D_{i,i} = 0$ - $D_{i,j} = D_{j,i} > 0$（$i \neq j$） - 输入的所有数值均为整数 ### 样例解释 1 如下所示移动，可以用总共 $78$ 分钟从城市 $1$ 移动到城市 $4$。 - 从城市 $1$ 到城市 $3$ 使用公司用车，需要 $2 \times 8 = 16$ 分钟。 - 从城市 $3$ 到城市 $2$ 使用公司用车，需要 $3 \times 8 = 24$ 分钟。 - 从城市 $2$ 到城市 $4$ 使用电车，需要 $5 \times 5 + 13 = 38$ 分钟。 无法在 $78$ 分钟以内从城市 $1$ 到城市 $4$。 由 ChatGPT 4.1 翻译