There are
buildings in the city Tommy is living at, and the
building has a height of
. Initially, Tommy is at building
, and he wants to go to building
. He can spend
and go to the leftmost building higher than the current building, where the distance between the two buildings is at most
(i.e., if Tommy is currently at building
, he can go to building
, which is the first building on the right of
building higher than
and
with a cost of
). Also, if Tommy is at the
building, he can go to the
building or the
building with a cost of
if these buildings exist. Help Tommy find the minimum cost to go to building
.
Constraints


Subtask 1 [20%]

Subtask 2 [80%]
No additional constraints.
Input Specification
The first line will contain four space-separated integers,
,
,
, and
.
The second line will contain
space-separated integers,
, respectively.
Output Specification
Output the minimum cost for Tommy to go to building
.
Sample Input
Copy
5 3 1 2
1 2 5 4 3
Sample Output
Copy
4
Comments
The problem statement should say
Shouldn't the problem statement say "He can spend
and go to the rightmost building higher than the current building....."? It says "leftmost" instead of "rightmost."