Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

PUBG Lover Programmer: The Beginning

By jisan047 · Limits 1s, 512 MB

Sroud loves to play PUBG and does programming contest. He always thinks about converting gameplay to programming, and most of the times he gets weird idea. The problem mentioned below is the output of one of those weird ideas.

In PUBG there are several play zones, and players should cross these play zones from starting to final play zone by car (if he has one) or by running. But in this special weird idea, one always has a car with him. But there are some weird instructions also to drive a car.

  1. The road is straight.
  2. There is only one button for a car, by pressing the button (as many time as one wants) the car moves exactly X meter forward.
  3. The only dependency is that, the car from any play zone cannot move to another play zone(Remember, one will get a new car at the starting of each play zone). i.e you can not press the button if there is a possibility to cross the play zone with car. So the remaining path has to be covered by running.

Now, Sroud is excited to find the size of path one has to cover by running to cross each play zone from starting to final play zone.

Input

Input starts with an Integer N and X denoting the number of play zones and the size of path a car moves forward by pressing the button mentioned above.
Second line contains N space separated integers a1, a2,…, aN, where ai denotes the size of the ith play zone.

Constraints:

1 ≤ N ≤ 2×105
(1 ≤ ai, X ≤ 109)

Output

Print an integer k — denoting the size of path one has to cover by running.

Sample

InputOutput
3 8
4 10 1 
7

Discussion

Statistics


93% Solution Ratio

Riaz_BSMRSTUEarliest, 4w ago

ishtupeedFastest, 0.0s

Riaz_BSMRSTULightest, 131 kB

mdvirusShortest, 99B

Submit

Login to submit