分数: 233 分
问题陈述
高桥立志成为一名登山运动员,目前正在接受训练。高桥参加的健身房有 N 会员,并且每个会员都有一个记录 最大可达高度 (以下简称“海拔”)。高桥是会员号 1,他当前的海拔高度是 P 米。会员号海拔高度 i (2 \leq i \leq N) is S_i 米。
高桥想通过向比他海拔更高的前辈学习来提高自己的海拔。具体来说,高桥可以重复以下操作任意次数(包括 0 次):
- 选择一名海拔为 严格大于 比高桥当前的海拔高,并向该成员学习。学习的结果是,高桥的海拔变得等于该成员的海拔。然而,每次这样的操作成本 C 日元作为课程费。
请注意,除了高桥以外的成员的海拔高度不会通过这些操作而改变。
高桥希望他的最终高度至少为 T 米。如果 P \geq T 已成立,无需任何操作。找出实现该目标所需的最低总课程费用。
如果无论怎样操作都无法达到目标,则输出 -1.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P \leq 10^9
- 1 \leq T \leq 10^9
- 1 \leq C \leq 10^9
- 1 \leq S_i \leq 10^9 (2 \leq i \leq N)
- 所有输入值均为整数
输入
N P T C S_2 S_3 \cdots S_N
- 第一行包含成员总数 N, 高桥当前海拔高度 P,目标高度 T,以及每次操作的课程费用 C,用空格分隔。
- 第二行包含海拔高度 S_2, S_3, \ldots, S_N 会员编号 2 通过 N,用空格分隔。然而,如果 N = 1,没有给出第二行(因为除了高桥之外没有其他成员)。
输出
一行输出使高桥的海拔至少所需的最低总课费 T 米。如果目标无法实现,则输出 -1.
示例输入 1
5 100 500 1000 200 300 500 150
示例输出 1
1000
示例输入 2
4 1000 2000 500 800 900 950
示例输出 2
-1
示例输入 3
10 50 1000000000 100000 1000 5000 10000 100000 1000000 10000000 100000000 500000000 1000000000
示例输出 3
100000