AT_abc325_e [ABC325E] Our clients, please wait a moment

[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} $

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

### 制約 - $ 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 $ に移動することはできません。