尊敬的客户,请稍等

题目描述

某国有 $N$ 个城市。

你要从城市 $1$ 的办公室出发,途经零个或多个城市,前往城市 $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}$

输出格式

以整数形式输出答案。

样例

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

78

可以按如下方式移动,从城市 $1$ 到城市 $4$ 总共花费 $78$ 分钟:

• 乘公司用车从城市 $1$ 到城市 $3$。耗时 $2 \times 8 = 16$ 分钟。
• 乘公司用车从城市 $3$ 到城市 $2$。耗时 $3 \times 8 = 24$ 分钟。
• 乘火车从城市 $2$ 到城市 $4$。耗时 $5 \times 5 + 13 = 38$ 分钟。

无法在 $78$ 分钟以内从城市 $1$ 到达城市 $4$。

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

1

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

168604826785

数据范围

• $2 \le N \le 1000$
• $1 \le A, B, C \le 10^6$
• $D_{i,j} \le 10^6$
• $D_{i,i} = 0$
• $D_{i,j} = D_{j,i} \gt 0$ $(i \neq j)$
• 所有输入值均为整数