一个国家里有 $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}$
```
- $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)$

将答案打印为整数。
（时间复杂度不超过1e8即可通过）

输入2：
3 1 1000000 1000000
0 10 1
10 0 10
1 10 0
输出2：
1