题目描述

强哥在 Russland 的小学留学毕业啦！在回到 Joyskid 之前，强哥想在 Russland 进行一次旅游。

Russland 是一个很大的国家，总共有 $n$ 座城市，强哥计划从 Moskau（1 号城市） 前往 Chita（$n$ 号城市），然后从 Chita 坐飞机回到他的老家 Joyskid。

任两座不同城市之间都会有两条不同方向的道路，且长度一定是一样的。我们假设城市 $i$ 和城市 $j$ 之间的道路长度是 $D_{i,j}$。

Russland 的长途汽车费用有一个参数 $A$，而火车费用有两个参数 $B,C$，由此得出：

• 城市 $i$ 和城市 $j$ 之间直行的汽车需要花费 $A\times D_{i,j}$ 卢布
• 城市 $i$ 和城市 $j$ 之间直行的火车需要花费 $B\times D_{i,j}+C$ 卢布

由于临近 Chita 的地区的公路状况实在是太糟糕，所以强哥离开某个城市时一旦决定坐火车，之后的旅程就不会再坐汽车了。

强哥想知道他的旅途最少需要花多少卢布。

输入格式

输入的第一行为四个正整数 $N,A,B,C$。

然后 $N$ 行，其中的第 $i$ 行第 $j$ 个数为 $D_{i,j}$。

输出格式

强哥至少花费的卢布数量。

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

78

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\ \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)$