[ABC325E] Our clients, please wait a moment

### 题目描述 一个国家里有 $n$ 个城市。 你需要从 $1$ 号城市旅行到 $n$ 号城市。 你有坐车和坐火车两种通行方式，对于从城市 $i$ 到城市 $j$ ： + 坐车会花费 $D_{i,j} \times A$ 分钟 + 坐火车会花费 $D_{i,j} \times B+C$ 分钟 你可以在不花费任何时间的情况下从坐车切换为坐火车，但不能从坐火车切换为坐车。 问从城市 $1$ 到城市 $n$ 最少需要几分钟？

[problemUrl]: https://atcoder.jp/contests/abc325/tasks/abc325_e ある国には都市が $ N $ 個あります。 あなたは、都市 $ 1 $ にある営業所から $ 0 $ 個以上の都市を経由して都市 $ N $ にある訪問先へ移動しようとしています。 移動手段は社用車と電車の $ 2 $ 種類があります。都市 $ 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} $

答えを整数として出力せよ。

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

### 制約 - $ 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) $ - 入力される数値はすべて整数 ### Sample Explanation 1 以下のように移動することで合計 $ 78 $ 分で都市 $ 1 $ から都市 $ 4 $ に移動することができます。 - 都市 $ 1 $ から都市 $ 3 $ まで社用車で移動する。この移動には $ 2\ \times\ 8\ =\ 16 $ 分かかる。 - 都市 $ 3 $ から都市 $ 2 $ まで社用車で移動する。この移動には $ 3\ \times\ 8\ =\ 24 $ 分かかる。 - 都市 $ 2 $ から都市 $ 4 $ まで電車で移動する。この移動には $ 5\ \times\ 5\ +\ 13\ =\ 38 $ 分かかる。 $ 78 $ 分未満の時間で都市 $ 1 $ から都市 $ 4 $ に移動することはできません。