409767: GYM103736 H Optimal Biking Strategy

Alice is going to go to the supermarket, which is $$$p$$$ meters away from her. She can walk or ride a bike. There are $$$n$$$ bike stops on the road, and she can only get on and off at these stops if she rides a bike.

She needs to pay to ride a bike. One yuan allows riding at most $$$s$$$ meters(less than $$$s$$$ meters costs one yuan, too). Formally, if two stops are $$$x$$$ meters away from each other and Alice chooses to bike, it costs her $$$\lceil\frac{x}{s}\rceil$$$ yuan.

Now, she has $$$k$$$ yuan, and she wants to know, what is the minimum number of meters to walk.

The first line contains three integers $$$n, p, s$$$ $$$(1 \le n \le 10^6, 1 \le p \le 10^9,1\le s \le 10^9)$$$ indicating the number of the bike shops, the location of the store, and maximum meters that one yuan allows to ride.

The second line contains $$$n$$$ integers, $$$a_1, a_2, \cdots, a_n$$$ $$$(0 \le a_i \le p)$$$ indicating the position of the $$$i$$$-th stop ($$$\forall i< j, a_i< a_j$$$).

The third line contains an integer $$$k(1\le k \le 5)$$$, indicating Alice has $$$k$$$ yuan.

Output one line containing one integer indicating the minimum number of meters that Alice needs to walk.

1 10 10
2
5

10

3 100 10
80 99 100
2

80

4 10 3
1 2 6 7
1

9

In the first test case, Alice cannot find any other bike stops to get off, so she has to walk $$$10$$$ meters.

In the second test case:

Alice can walk $$$80$$$ meters and then pay two yuan to ride $$$20$$$ meters.

In the third test case, Alice can only ride from $$$1$$$ to $$$2$$$ or $$$6$$$ to $$$7$$$, so she has to walk the remaining $$$9$$$ meters.