Our clients, please wait a moment

There are $N$ cities in a certain country. You will travel from your office in city $1$ to a destination in city $N$, via zero or more cities. Two types of transportation are available: company car and train. The time required to travel from city $i$ to city $j$ is as follows: * $D_{i,j} \times A$ minutes by company car, and * $D_{i,j} \times B + C$ minutes by train. You can switch from company car to train, but not vice versa. You can do so without spending time, but only in a city. What is the minimum time in minutes to travel from city $1$ to city $N$? ## Constraints * $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)$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $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}$ [samples]