Dirty Driving

Time limit1sMemory limit128 MB

Summary

Given distances to n cars ahead and a constant p, find the minimum gap to the nearest car so every car x ahead is at least p*(k+1) away, where k counts cars between.

Level: Medium5 of 10
Topics: Sorting, Greedy, Math
Solved: No attempts yet

Problem

Like every other good driver, you love to honk your horn and shout at the drivers around you. Right now you are stuck at the back of a long line, fuming at everyone else's inability to keep a proper distance from the car in front of them. But are you really keeping a safe distance yourself?

You have worked out that, in order to never have to hit your brakes, the distance you keep to any car $x$ ahead of you must be at least $p \cdot (n + 1)$ , where $n$ is the number of cars between you and car $x$ , and $p$ is an integer constant that depends on which of your cars you are currently driving.

The cars ahead never change their positions relative to one another, so the only thing you can adjust is your own distance to the car directly in front of you. Given $p$ and the current distance to every car ahead (listed in arbitrary order), compute the minimum distance you must keep to the car directly in front so that you never have to use your brakes.

Input

The first line contains two integers $n$ and $p$ ( $1 \le n \le 100000$ , $1 \le p \le 20$ ): the number of cars ahead of you and the deceleration constant.

The second line contains $n$ distinct integers, the current distance from you to each car ahead. Each distance lies in the interval $[1, 10^7]$ .

Output

Output a single integer: the minimum distance you must keep to the car directly in front of you so that you never have to use your brakes.

Examples2

Example 1
Input
```
3 1
1 2 4
```
Expected output
```
1
```
Example 2
Input
```
6 3
2 3 4 5 6 1
```
Expected output
```
13
```