题目描述

农夫约翰以及他的 $N(1 \le N \le 2500)$ 头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。

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

当约翰一个人坐在木筏上，他把木筏划到对岸需要 $M(1 \le M \le 1000)$ 分钟。当木筏搭载的奶牛数目从 $i-1$ 增加到 $i$ 时，约翰得多花 $M_i(1 \le M_i \le 1000)$ 分钟才能把木筏划过河（也就是说，船上有 $1$ 头奶牛时，约翰得花 $M+M_1$ 分钟渡河；船上有 $2$ 头奶牛时，时间就变成 $M+M_1+M_2$ 分钟。后面的以此类推）。那么，约翰最少要花多少时间，才能把所有奶牛带到对岸呢？当然，这个时间得包括约翰一个人把木筏从对岸划回来接下一批的奶牛的时间。

输入格式

• 第一行包含 $2$ 个整型变量 $N$ 和 $M$。
• 第二行包含 $2 ... N + 1$ 个整数，第 $i + 1$ 行包含 $1$ 个整数 $M_i$。

输出格式

• 输出共 $1$ 行，为农夫约翰让所有奶牛过河所需的最短时间。

5 10 
3 
4 
6 
100 
1

50

提示

有五头牛。农夫约翰独自渡河需要10分钟，13只带一头牛，17只带两头，23只带三头牛，123只带四头牛，124只带五头牛。 农夫约翰可以先与三头牛传中（23分钟），然后返回（10分钟），再与最后两只奶牛传中（17分钟）。23+10+17=总共50分钟。