We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Police Operation

Police Operation

Roy is helping the police department of his city in crime fighting. Today, they informed him about a new planned operation.

Think of the city as a plane. The road along the -axis is very crime prone, because criminals live there. No two criminals live at the same position.

To catch these criminals, the police department has to recruit some police officers and give each of them USD as wages. A police officer can start his operation from any point , drive his car to point in a straight line, and catch all the criminals who live on this way. The cost of fuel used by the officer's car is equal to the square of the euclidean distance between points and (Euclidean distance between points and equals to ).

The police department asks Roy to plan this operation. So Roy has to tell them the number of officers to recruit and the routes these officers should take in order to catch all the criminals. Roy has to provide this information while minimizing the total expenses of this operation.

Find out the minimum amount of money required to complete the operation.

Input Format

The first line contains two integers , number of criminals, and , the cost of recruiting a police officer. The next line contains space separated integers. The integer indicates the position of the criminal on -axis (in other words, if the integer is , then location of the criminal is ). The value of the positions are between and and are given in increasing order in the input.

Output Format

Print the minimum amount of money required to complete the operation.

Sample Input

5 10
1 4 5 6 9

Sample Output

34

Explanation

For the sample test case, police department recruits officers who get paid . The first officer starts at point and catches the criminal there. So he does not use any fuel. The second officer catches criminals at points , and . He burns fuel worth USD . The third officer catches the criminal at point . He also does not burn any fuel. The total money spent by the department is, .

Timelimits

Timelimits for this challenge are given here