2400: 我们的客户，请稍等
[Creator : ]
Description
一个国家里有 $n$ 个城市。
你需要从 $1$ 号城市旅行到 $n$ 号城市。
你有坐汽车和坐火车两种通行方式，对于从城市 $i$ 到城市 $j$ ：
问从城市 $1$ 到城市 $n$ 最少需要几分钟？
你需要从 $1$ 号城市旅行到 $n$ 号城市。
你有坐汽车和坐火车两种通行方式，对于从城市 $i$ 到城市 $j$ ：
- 坐汽车会花费 $D_{i,j} \times A$ 分钟
- 坐火车会花费 $D_{i,j} \times B+C$ 分钟
问从城市 $1$ 到城市 $n$ 最少需要几分钟？
Input
输入格式如下:
```
$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)$
```
$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)$
Output
将答案打印为整数。
（时间复杂度不超过1e8即可通过）
（时间复杂度不超过1e8即可通过）
Sample Input Copy
4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0
Sample Output Copy
78
HINT
输入2： 3 1 1000000 1000000 0 10 1 10 0 10 1 10 0 输出2： 1