提示: 欢迎访问OurACM平台。
Problem 1416 飞机加油问题

Accept: 322    Submit: 1728
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

F国际航空公司在世界范围有n个国际机场。第i 个国际机场到中心机场的距离为di, i=1,…,n。从国际机场j 到国际机场i 的飞行费用为c(i,j) = s + (dj - di)2 ,s 为地面加 油费用。从任何国际机场飞往中心机场的飞机可以在任一国际机场加油后继续飞行。飞机加 油问题要求确定从距中心机场最远的国际机场飞到中心机场的最少费用。

编程任务:

对于给定的n个国际机场到中心机场的距离d1,d2,...,dn ,以及地面加油费用s,编程 计算从距中心机场最远的国际机场飞到中心机场的最少费用。

Input

第一行有2 个整数n (n<=400,000)和s,表示有n个国际机场(不包 括中心机场),地面加油费用s。接下来的1行中每行有n个整数d1,d2,...,dn,表示给定的 n个国际机场到中心机场的距离。

Output

将编程计算出的最小费用输出。

Sample Input

5 10 1 3 6 7 10

Sample Output

64

Source

FJ CFCS 2006

Submit  Back  Status  Discuss