Cows Across the River

Farmer John is trying to transport his N cows across a river using a single raft. He must always be on the raft during every crossing. However, the more cows he takes with him, the slower the crossing becomes. When Farmer John rides the raft alone, it takes M minutes to cross the river. When he takes i cows, the raft takes an additional time given by M_i minutes compared to when it carried i-1 cows. In other words, the time to cross with i cows is given by

\(T(i)=M+\sum_{j=1}^{i} M_j\)

Your task is to determine the minimum total time required for Farmer John to get all his cows to the other side of the river. Note that after a trip carrying cows, if there are still cows left to transport, Farmer John must return alone, which takes M minutes.

inputFormat

The first line contains two integers N and M where 1 \leq N \leq 2500 and 1 \leq M \leq 1000. The second line contains N integers: M₁, M₂, ..., M_N where 1 \leq M_i \leq 1000.

outputFormat

Output a single integer: the minimum total time required for Farmer John to transport all the cows to the other side of the river.

sample

3 10
5 3 7

25