Scales

Farmer John has a balance for weighing cows. He also has a set of $N$ weights ($1 \le N \le 1000$) with known masses. Every mass fits in 31 bits. To weigh a cow, he places the cow on one side of the balance and adds weights to the other side until the two sides balance. Weights cannot go on the same side as the cow, because cows kick weights in his face whenever they can.

The balance has a maximum mass rating. If the total mass on one side exceeds $C$ ($1 \le C < 2^{30}$), the balance breaks.

The weights have a special property. When sorted from smallest to largest, each weight from the third one onward has a mass at least as large as the sum of the previous two weights.

Find the largest mass that can be measured exactly with these weights. The total mass used must not exceed $C$, so he may not be able to place every weight on the scale. Given the list of weights and the maximum mass $C$, output the largest legal mass that can be weighed exactly.

The first line contains two positive integers $N$ and $C$, separated by a space.

Each of the next $N$ lines contains one positive integer, the mass of one weight. The masses are given in non-decreasing order.

Print one integer on the first line: the largest mass that can be measured accurately and safely.