/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は登山家を目指しており、現在トレーニング中です。高橋君が通うジムには N 人の会員がおり、各会員には到達可能な最高標高（以下、単に「標高」と呼びます）が記録されています。高橋君は会員番号 1 であり、現在の標高は P メートルです。会員番号 i (2 \leq i \leq N) の標高は S_i メートルです。
高橋君は、自分よりも高い標高を持つ先輩会員に師事することで、自分の標高を上げたいと考えています。具体的には、高橋君は以下の操作を好きな回数（ 0 回でもよい）繰り返し行うことができます。
- 現在の高橋君の標高よりも真に大きい標高を持つ会員を 1 人選び、その会員に師事する。師事した結果、高橋君の標高は、その会員の標高と同じ値になる。ただし、この操作には 1 回につき 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
- 1 行目には、会員の総数を表す整数 N 、高橋君の現在の標高を表す整数 P 、目標標高を表す整数 T 、 1 回の操作にかかるレッスン料を表す整数 C が、スペース区切りで与えられる。
- 2 行目には、会員番号 2 から N までの各会員の標高 S_2, S_3, \ldots, S_N が、スペース区切りで与えられる。ただし、 N = 1 の場合、 2 行目は与えられない（高橋君以外の会員がいないため）。
出力
高橋君の標高を T メートル以上にするために必要な最小の総レッスン料を 1 行で出力してください。目標を達成できない場合は -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
Score : 233 pts
Problem Statement
Takahashi aspires to become a mountaineer and is currently in training. The gym Takahashi attends has N members, and each member has a recorded maximum reachable altitude (hereafter simply called "altitude"). Takahashi is member number 1, and his current altitude is P meters. The altitude of member number i (2 \leq i \leq N) is S_i meters.
Takahashi wants to increase his altitude by learning from senior members who have a higher altitude than his. Specifically, Takahashi can repeat the following operation any number of times (including 0 times):
- Choose one member whose altitude is strictly greater than Takahashi's current altitude, and learn from that member. As a result of learning, Takahashi's altitude becomes equal to that member's altitude. However, each such operation costs C yen as a lesson fee.
Note that the altitudes of members other than Takahashi do not change through these operations.
Takahashi wants his final altitude to be at least T meters. If P \geq T already holds, no operations are needed. Find the minimum total lesson fee required to achieve the goal.
If it is impossible to achieve the goal no matter how the operations are performed, output -1.
Constraints
- 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)
- All input values are integers
Input
N P T C S_2 S_3 \cdots S_N
- The first line contains the total number of members N, Takahashi's current altitude P, the target altitude T, and the lesson fee per operation C, separated by spaces.
- The second line contains the altitudes S_2, S_3, \ldots, S_N of members numbered 2 through N, separated by spaces. However, if N = 1, the second line is not given (since there are no members other than Takahashi).
Output
Output in one line the minimum total lesson fee required to make Takahashi's altitude at least T meters. If the goal cannot be achieved, output -1.
Sample Input 1
5 100 500 1000 200 300 500 150
Sample Output 1
1000
Sample Input 2
4 1000 2000 500 800 900 950
Sample Output 2
-1
Sample Input 3
10 50 1000000000 100000 1000 5000 10000 100000 1000000 10000000 100000000 500000000 1000000000
Sample Output 3
100000