Like all other good drivers, Uolevi likes to curse, swear and honk his horn at his fellow automobile drivers. Today Uolevi is at the rear of a long line, brooding over the others’ inability to keep proper distance to the car in front. But is Uolevi really keeping his own distance?

Uolevi has calculated that in order to never have to use his breaks, he must keep a distance at least $p(k + 1)$ to any car $x$ in front of him where $k$ is the number of cars between Uolevi and $x$, and $p$ is an integer constant determined by which of his cars Uolevi is currently driving. Given the value of $p$ and the distances to each of the cars ahead of Uolevi, calculate the minimum distance Uolevi should be keeping to the car directly in front, in order to not have to use breaks.

Input

The first line of input contains two integers, $n$ and $p$, where $n$ is the number of cars in front of Uolevi. Next line contains $n$ unique integers $a_1, \ldots, a_n$ denoting the current distance to each of the cars ahead of Uolevi.

Output

Output the minimum distance Uolevi must keep to the car directly in front, in order to not have to use his breaks.

Constraints

• $1 \le n \le 10^5$
• $1 \le p \le 20$
• $1 \le a_i \le 10^7$

Examples

Input:

3 1
1 2 4

Output:

1

Input:

6 3
2 3 4 5 6 1

Output:

13