题目描述

Keda 在为同学们计划 2025 的旅学活动，预计从深圳出发，终点站在北京，这里为了方便称呼可以把深圳称呼为 $1$ 号点，北京称呼为 $n$ 号点，接下来会给你一个 $n \times n$ 的邻接矩阵代表两点之间的距离。

但是如果光是这样那岂不是就是一个普通的最短路了？那可不行。

我们这里规定，你从 $i$ 到 $j$ 可以选择步行，那么花费的时间就是 $a_{i,\ j} \times A$，如果选择坐汽车那么花费的时间就是 $a_{i,\ j} \times B + C$。你可以不花费任何时间从步行切换称为坐汽车，但是不可以从坐汽车切换成为步行。

请问你从深圳到北京的最小花费的时间是多少？

输入格式

第一行四个整数 $n,\ A,\ B,\ C$ 含义如题目描述所示。

接下来 $n$ 行，每行 $n$ 个整数代表 $a$ 数组。

输出格式

请输出你所需要花费的最小时间。

样例

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

78

样例解释

首先我们从 $1$ 到 $3$ 步行花费 $2 \times 8 = 16$ 的时间。

我们接下来从 $3$ 到 $2$ 步行花费 $3 \times 8 = 24$ 的时间。

最后我们从 $2$ 坐汽车到 $4$ 花费 $5 \times 5 + 13 = 38$ 的时间。

总时间花费为 $78$。

数据范围

$2 \le n \le 10^{3}$，$1 \le a,\ b,\ c \le 10^{6}$。

$if\ i = j: a_{i,\ j} = 0$。

$if\ i \neq j: 0 < a_{i,\ j} = a_{j,\ i} \le 10^{6}$。