{"problem":{"name":"Our clients, please wait a moment","description":{"content":"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 ca","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc325_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cities in a certain country.  \nYou will travel from your office in city $1$ to a destination in city $N$, via zero or more cities.  \nTwo types of transportation are available: company car and train. The time required to travel from city $i$ to city $j$ is as follows:\n\n*   $D_{i,j} \\times A$ minutes by company car, and\n*   $D_{i,j} \\times B + C$ minutes by train.\n\nYou can switch from company car to train, but not vice versa.  \nYou can do so without spending time, but only in a city.\nWhat is the minimum time in minutes to travel from city $1$ to city $N$?\n\n## Constraints\n\n*   $2 \\leq N \\leq 1000$\n*   $1 \\leq A, B, C \\leq 10^6$\n*   $D_{i,j} \\leq 10^6$\n*   $D_{i,i} = 0$\n*   $D_{i,j} = D_{j,i} > 0$ $(i \\neq j)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $A$ $B$ $C$\n$D_{1,1}$ $D_{1,2}$ $\\ldots$ $D_{1,N}$\n$D_{2,1}$ $D_{2,2}$ $\\ldots$ $D_{2,N}$\n$\\vdots$\n$D_{N,1}$ $D_{N,2}$ $\\ldots$ $D_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc325_e","tags":[],"sample_group":[["4 8 5 13\n0 6 2 15\n6 0 3 5\n2 3 0 13\n15 5 13 0","78\n\nYou can travel from city $1$ to city $4$ in a total of $78$ minutes by moving as follows.\n\n*   Travel by company car from city $1$ to city $3$. This takes $2 \\times 8 = 16$ minutes.\n*   Travel by company car from city $3$ to city $2$. This takes $3 \\times 8 = 24$ minutes.\n*   Travel by train from city $2$ to city $4$. This takes $5 \\times 5 + 13 = 38$ minutes.\n\nIt is impossible to travel from city $1$ to city $4$ in less than $78$ minutes."],["3 1 1000000 1000000\n0 10 1\n10 0 10\n1 10 0","1"],["5 954257 954213 814214\n0 84251 214529 10017 373342\n84251 0 91926 32336 164457\n214529 91926 0 108914 57762\n10017 32336 108914 0 234705\n373342 164457 57762 234705 0","168604826785"]],"created_at":"2026-03-03 11:01:14"}}