题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

5 10
3
4
6
100
1

输出样例

50

提示

输入说明:

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

输出说明:

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