← 返回题目列表

AtCoder · awc0058_a

A. 登山训练

中文机器翻译题面 查看原题

分数: 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