Bob is a stressed CB student, because he is taking math and physics next octomester! Bob knows that he will need \(K\) days to study for a particular test, and that he can only study for one test on a particular day. He can also study for a different test the same day he is writing a particular test, but he may not study for a particular test the day he is writing that test, as Bob always writes his tests first thing in the morning.

To face this upcoming octomester, Bob needs to study ahead! Given the days where tests are going to occur, how many days in advance of the first test should he begin studying to make sure he studies the full \(K\) days he needs for each test? Note that there will always be a test on day \(1\).

Input Specification

The first line of input will contain two integers \(N\) \((1 \le N \le 10^5)\), and \(K\) \((1 \le K \le 10^5)\) indicating the days on which Bob has tests, and the number of days Bob needs to study before each test.

The next line will contain \(N\) integers ranging from \(1\) to \(10^9\) inclusive, denoting the days on which Bob has tests. One of the numbers is guaranteed to be \(1\), as Bob always has a test on the first day back.

Output Specification

Output an integer, the minimum number of days Bob needs to study before the first test.

Subtask 1 [20%]

\(1 \le N \le 1000\)

Subtask 2 [80%]

No additional constraints. Note that long long is needed for this subtask, as the numbers do get large enough to cause integer overflow. This only applies to strongly typed languages like C++.

Sample Input 1

5 1
1 2 3 4 5

Sample Output 1

1

Sample Explanation 1

Bob will need to study \(1\) day ahead of the first test to prepare for it, and can study for the second test the day he writes the first test. Next day when he writes the second test, he can study for the third test, etc.

Sample Input 2

3 3
2 2 1

Sample Output 2

8

Sample Explanation 2

Bob needs \(3\) days before day \(1\) to study for the first test. He can study \(1\) day for one of the tests on day \(2\), but he will need \(5\) more days in order to study \(3\) days for both tests on day \(2\). Thus he must study those \(5\) days before day \(1\), resulting in a total of \(8\) days of studying before day \(1\).

Sample Input 3

5 3
1 2 6 6 10

Sample Output 3

7