题目描述

$\red{Farmer John}$以及他的$\red{N(1 <= N <= 2,500)}$头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。

由于奶牛不会划船，在整个渡河过程中，$\red{FJ}$必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加$\red{1，}$$\red{FJ}$把木筏划到对岸就得花更多的时间。

当$\red{FJ}$一个人坐在木筏上，他把木筏划到对岸需要$\red{M(1 <= M <= 1000)}$分钟。当木筏搭载的奶牛数目从$\red{i-1}$增加到$\red{i}$时，$\red{FJ}$得多花$\red{M_i(1 <= M_i <= 1000)}$分钟才能把木筏划过河（也就是说，船上有$\red{1}$头奶牛时，$\red{FJ}$得花$\red{M+M_1}$分钟渡河；船上有$\red{2}$头奶牛时，时间就变成$\red{M+M_1+M_2}$分钟。后面的依此类推）。

那么，$\red{FJ}$最少要花多少时间，才能把所有奶牛带到对岸呢？当然，这个时间得包括$\red{FJ}$一个人把木筏从对岸划回来接下一批的奶牛的时间。

输入格式

第$\red{1}$行: $\red{2}$个用空格隔开的整数：$\red{N }$和 $\red{M}$

第$\red{2..N+1}$行: 第$\red{i+1}$为$\red{1}$个整数：$\red{M_i}$

输出格式

第$\red{1}$行: 输出$\red{1}$个整数，为$\red{FJ}$把所有奶牛都载过河所需的最少时间

样例

输入样例

5 10
3
4
6
100
1

输出样例

50

提示

输入说明:

$\red{FJ}$带了$\red{5}$头奶牛出门。如果是单独把木筏划过河，$\red{FJ}$需要花$\red{10}$分钟，带上$\red{1}$头奶牛的话，是$\red{13}$分钟，$\red{2}$头奶牛是$\red{17}$分钟，$\red{3}$头是$\red{23}$分钟，$\red{4}$头是$\red{123}$分钟，将 $\red{5}$头一次性载过去，花费的时间是$\red{124}$分钟。

输出说明:

$\red{Farmer John}$第一次带$\red{3}$头奶牛过河（$\red{23}$分钟），然后一个人划回来 （$\red{10}$分钟），最后带剩下的$\red{2}$头奶牛一起过河（$\red{17}$分钟），总共花费的时间是 $\red{23+10+17 = 50}$分钟。