Easy Problem

0

0 votes
Medium-Hard
Problem

Mr. M is on the mission, he needs to collect N flags that are located at different places in the city. Think of the city as a plane. No two flags will be at same position and all the flags are located on x axis.

To catch these Flag, Mr. M has to rent some taxis and give each of them cost of the fuel used by the taxi and some hiring amount(M). A driver can start his collection of flags from any point, and drive his car in a straight line, and catch all the flags who lie on this way. The cost of fuel used by the taxi is equal to the square of the euclidean distance between points (x1,y1) and (x2,y2) (Euclidean distance between points (x1,y1) and (x2,y2) equals to sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2)).

Now Mr. M is confused, and he needs your help to plan this operation. you have to decide the number of taxis to hire and routes of these taxis should take in order to catch all the flags.you have to plan this operation while minimising the total cost.

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

Input Format

The first line contains two integers n, number of flags, and M, the cost of hiring a taxi. The next line contains n space separated integers. The integer indicates the position of the ith flag on x-axis (in other words, if the integer is x, then location of the ith flag is (x,0) ). The value of the positions are between 1 to 10^9 and and are given in increasing order in the input.

Output Format

Print the minimum amount of money required to complete the collection of flags.

constraints

0 <= n <= 2*10^6

0 <= m<= 10^9

0 < xi < 10^9

Setter: Mohib Manva

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the sample test case, Mr M. recruits 2 taxis who get paid 2*10 = 20 hiring charge . The first taxi starts at point (1,0) and catches the flag there. So he does not use any fuel. The second taxi catches flag at points (4,0) ,(5,0) and (6,0). He burns fuel worth 4 unit . so, The total money spent by the department is, 20 + 4 = 24 .

Editor Image

?