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 翻译