[Usaco2008 Mar]River Crossing渡河问题

农夫约翰（FJ）和他的 $N$ 头奶牛需要渡过一条河，但他们唯一的渡河工具是一只木筏。

由于奶牛不会划船，在整个渡河过程中，FJ 必须始终在木筏上。木筏上搭载的奶牛越多，FJ 将木筏划到对岸所需的时间就越长。

当 FJ 独自划木筏过河时，需要花费 $M$ 分钟。当木筏搭载的奶牛数量从 $i-1$ 头增加到 $i$ 头时，渡河时间会增加 $M_i$ 分钟。因此，搭载 $i$ 头奶牛渡河所需的时间为：

M+\sum_{j=1}^{i}M_j。

例如，木筏上有 $1$ 头奶牛时，渡河需要 $M+M_1$ 分钟；有 $2$ 头奶牛时，需要 $M+M_1+M_2$ 分钟，依此类推。

FJ 可以将奶牛分成若干批运送。除最后一次渡河外，每运送完一批奶牛，FJ 都必须独自将木筏划回原岸，以接下一批奶牛。

请计算 FJ 将所有奶牛运到对岸所需的最少时间。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$ 。

接下来 $N$ 行，第 $i$ 行包含一个整数 $M_i$ ，表示木筏搭载的奶牛数量从 $i-1$ 头增加到 $i$ 头时，渡河时间增加的分钟数。

输出一个整数，表示 FJ 将所有奶牛运到对岸所需的最少时间。

5 10
3
4
6
100
1

输入说明:

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

FJ 第一次带 $3$ 头奶牛过河，花费 $23$ 分钟；随后独自划木筏返回，花费 $10$ 分钟；最后带剩余的 $2$ 头奶牛过河，花费 $17$ 分钟。

因此最少总时间为：

23+10+17=50。

本题为 USACO 2008 年 3 月试题「River Crossing」，题面与测试数据整理自 BZOJ 1617。

5 10
3
4
6
100
1

输入说明:

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