#P8743. B
B
Problem B:数轴上的环
题目描述
数轴上有 个点,编号为 到 。令 ,对于 ,有 。因此, 为负数时,第 个点位于第 个点的左侧;不同编号的点可以位于同一坐标。
请选择恰好 个不同编号的点,并将它们按某种顺序连接成一个环。例如,可以按 的顺序连接。
环上相邻两点 的距离为 。基础收益为环上全部相邻点对的距离之和,包括最后一个点到第一个点的距离。
对于环上的每个点,如果它的前驱、后继的编号均比它小,或者均比它大,再获得 的收益。 可以为负数,此时这项收益为负。
求最大总收益。只需输出收益,不需要输出连接方案。
当 时,唯一的点的前驱、后继均为它自己,距离和及额外收益均为 。当 时,两点之间的距离计入两次,两个点均获得额外收益。
输入格式
第一行两个整数 。
第二行 个整数 。前 个数给出坐标差,最后一个数为额外收益。
输出格式
输出一行一个整数,表示最大总收益。答案可能为负数。
样例
4 2
1 1 -1 1
6
数据范围
,。
本题评测时限为 秒,内存限制为 MiB。