Strange Function

3.7

57 votes
Ready, Mathematics, Open, Approved, Easy-Medium, Mathamatics
Problem

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 |Ai - Bi| ≤ C.

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

Strange Function

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 Ai.

Output format:

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

Constraints:

  • 1 ≤ N ≤ 105
  • 0 ≤ Ai , C ≤ 107
  • N ≤ 500 in test data worth 20% of all points
  • N ≤ 2000 in test data worth 40% of all points
Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?