River Crossing

Farmer John needs to move his $N$ cows ($1 \le N \le 2500$) across a river. Only a single raft is available, and Farmer John must be aboard for every crossing.

Adding cows to the raft slows it down. With Farmer John alone, the raft crosses the river in $M$ minutes ($1 \le M \le 1000$). Loading cows one at a time, the $i$-th cow added makes the crossing take $M_i$ more minutes ($1 \le M_i \le 1000$) than it would with $i-1$ cows. So a raft carrying $k$ cows crosses in $M + M_1 + M_2 + \cdots + M_k$ minutes. The cows are interchangeable: only how many ride together matters, and the marginal costs apply in the given order $M_1, M_2, \ldots$

Farmer John may ferry the cows over in several trips; after each trip except the last he rows back alone, which also takes $M$ minutes. Determine the minimum total time to get all $N$ cows across, including the return trips.

• Line 1: two space-separated integers $N$ and $M$.
• Lines 2 to $N+1$: line $i+1$ contains a single integer $M_i$.

• A single line: the minimum total time to move all cows across the river.

Suppose there are five cows and the crossing times build up like this: Farmer John alone takes 10 minutes, with one cow 13, with two 17, with three 23, with four 123, and with all five 124. One good plan is to cross with three cows (23 minutes), return alone (10 minutes), then cross with the remaining two (17 minutes), for a total of $23 + 10 + 17 = 50$ minutes.