Kevin has an array A of N integers.

To make his array better Kevin can change every element by at most C. Formally, he can get any array B such that |A_i - B_i| ≤ C.

He wants to find the maximum of the following function among all possible arrays B:

Input format:

The first line of the input contains two space-separated integers N and C. The second line of the input contains N space-separated integers A_i.

Output format:

Output the single integer -- the maximum of the function.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ A_i , C ≤ 10⁷
• N ≤ 500 in test data worth 20% of all points
• N ≤ 2000 in test data worth 40% of all points