P5194 [USACO05DEC] Scales S

John has a scale for weighing cows. Along with it, he has $N \ ( 1 \leq N \leq 1000 )$ weights with known masses (all weight values are within the range of 32-bit signed integers). Each time he weighs a cow, he puts the cow on one side of the scale, then adds weights to the other side until the scale balances. At that moment, the total mass of the weights is the cow’s mass (John cannot put weights on the cow’s side, because cows do not like being weighed. Whenever John puts a weight under her hooves, she will try to kick it into John’s face). The scale cannot hold an unlimited mass. If the mass on either side of the scale exceeds $C \ ( 1 \leq C \leq 2^{30} )$, the scale will be damaged. The weights are arranged in a line in non-decreasing order of mass. Also, starting from the 3rd weight, each weight’s mass is at least the sum of the masses of the two largest weights before it (that is, the two heaviest weights with smaller mass). John wants to know the maximum mass that can be weighed using the weights he has and this scale. Since the maximum load of the scale is $C$, he cannot put all weights on the scale. Now John tells you the mass of each weight and the maximum mass the scale can support. Your task is to choose some weights so that their total mass is as large as possible among all choices, without breaking the scale.

The 1st line contains two positive integers $N$ and $C$, separated by spaces. Lines $2$ to $N+1$: each line contains one positive integer, the mass of a weight. It is guaranteed that these masses form a non-decreasing sequence.

Output one positive integer, the maximum mass that can be weighed without breaking the scale using the given weights.

Translated by ChatGPT 5