题目描述

强哥所在的城市群有 $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}$

输出格式

输出一个整数，表示最短出行时间。

输入输出样例

样例 1

输入

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$ 分钟 总时间：$16 + 24 + 38 = 78$ 分钟

样例 2

输入

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

输出

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

输出

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$）
• 所有输入均为整数