PUBG Lover Programmer: The Beginning

jisan047 BSMRSTU Home Quarantine C...
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 XX 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 NN (1N2×1051 ≤ N ≤ 2×10^5) and XX (1X1091 ≤ X ≤ 10^9) denoting the number of play zones and the size of path a car moves forward by pressing the button mentioned above.

Second line contains NN space separated integers a1a_1, a2a_2, ..., aNa_N, where aia_i (1ai1091 ≤ a_i ≤ 10^9) denotes the size of the ii-th play zone.

Output

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

Sample

InputOutput
3 8
4 10 1 
7

Submit

Login to submit.

Statistics

91% Solution Ratio
Riaz_BSMRSTUEarliest, May '20
ishtupeedFastest, 0.0s
Riaz_BSMRSTULightest, 131 kB
Roboter404Shortest, 75B
Toph uses cookies. By continuing you agree to our Cookie Policy.