#P18190. Train Seats
Train Seats
Train Seats
有 把椅子排成一行,从左到右编号为 。有 个人,编号为 。第 个人将坐在椅子 上,不同的人所坐的椅子互不相同。
最初所有椅子都没有人。所有人按照某个顺序依次入座。
当一个人入座时,设其左边最近的已有人入座的椅子编号为 ,右边最近的已有人入座的椅子编号为 。如果左边没有已入座的人,令 ;如果右边没有已入座的人,令 。这个人获得的分数为 。
共有 种入座顺序。求所有人分数总和的最大可能值。
输入格式
第一行两个整数 。
第二行 个整数 。
输出格式
输出一个整数,表示最大的总分。
数据范围
- ;
- ;
- ;
- 当 时,;
- 所有输入均为整数。
输入中的 不保证已经排序。
样例 1
输入
3 10
3 7 10
输出
28
例如,依次让第 3、1、2 个人入座:
- 第 3 个人入座时,,得分为 ;
- 第 1 个人入座时,,得分为 ;
- 第 2 个人入座时,,得分为 。
总分为 ,可以证明这已是最大值。
样例 2
输入
5 20
3 10 11 14 17
输出
73
样例 3
输入
10 1000000000
136909656 243332691 643531997 505919307 43553384 657638276 57213246 179732866 357373203 182482400
输出
7649951260