小明计划准备旅游，小明的国家有 n 个城市。
小明需要从 1 号城市旅行到 n 号城市。
小明有坐车和坐火车两种通行方式，对于从城市 i 到城市 j ：
+ 坐车会花费 D_{i,j} \times A 分钟
+ 坐火车会花费 D_{i,j} \times B+C 分钟
小明可以在不花费任何时间的情况下从坐车切换为坐火车，但不能从坐火车切换为坐车。
问从城市 1 到城市 n 最少需要几分钟？
第一行四个数字，N,A,B,C；
接下来N行N列的剧中，表示从城市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
样例1解释：
您可以通过以下移动方式，在 78 分钟内从城市 1 到达城市 4 。
乘坐公司的汽车从城市 1 到城市 3 。耗时 2×8=16 分钟。
乘坐公司汽车从城市 3 前往城市 2 。耗时 3×8=24 分钟。
乘坐火车从城市 2 前往城市 4 。耗时 5×5+13=38 分钟。
从城市 1 到城市 4 不可能少于 78 分钟。