Background

Special for be# AT_abc325_e [ABC325E] Our clients, please wait a moment

题目描述

某国有 $N$ 个城市。
你打算从城市 $1$ 的营业所出发，经过 $0$ 个或多个城市，前往城市 $N$ 的访问地点。
你可以选择两种交通方式：公司用车和电车。从城市 $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}$

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

输出 #1

78

输入输出样例 #2

输入 #2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

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$）
• 输入的所有数值均为整数

样例解释 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$。

由 ChatGPT 4.1 翻译inners, ^_^

Description

Given two integers x and y, print the sum.

Format

Input

Two integers x and y, satisfying $0\leq x,y\leq 32767$ .

Output

One integer, the sum of x and y.

Samples

123 500

623

Limitation

1s, 1024KiB for each test case.