题目描述

某国有 $N$ 个城市。 你打算从城市 $1$ 的营业所出发，经过 $0$ 个或多个城市，前往城市 $N$ 的访问地点。 你可以选择两种交通方式：公司用车和电车。从城市 $i$ 到城市 $j$ 的所需时间如下：

• 使用公司用车时：$D_{i,j} \times A$ 分钟
• 使用电车时：$D_{i,j} \times B + C$ 分钟

但是，你可以从公司用车换乘到电车，但不能从电车换回公司用车。 此外，换乘只能在各个城市进行，且换乘不需要时间。

从城市 $1$ 到城市 $N$ 的最短所需时间是多少分钟？

输入格式

第一行输入四个整数 $N, A, B, C$，分别表示城市数量、乘坐公司用车的单位距离用时、乘坐电车的单位距离用时，以及每次乘坐电车的额外用时。

接下来输入 $N$ 行，每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数为 $D_{i,j}$，表示城市 $i$ 与城市 $j$ 之间的距离。

输出格式

请输出答案的整数值。

数据范围与约定

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

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

输出数据 1

78

输入数据 2

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

输出数据 2

1

输入数据 3

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

输出数据 3

168604826785