Maximum Weight Measurement

John owns a balance scale used to measure the weight of his cows. He places a cow on one side of the scale and then adds a selected subset of his weights to the other side until the scale is balanced. Since the cow refuses to be weighed with weights on its side, only the weights can be placed on the opposite pan. The total mass of the weights used is therefore the cow’s weight.

However, the scale has a weight limit. If the mass on one side exceeds C, the scale will be damaged. John has N weights (where \(1 \le N \le 1000\)) with known masses (each within the 32-bit signed integer range). The weights are arranged in non-decreasing order and, starting from the third weight, every weight is at least as heavy as the sum of the previous two weights, i.e. for every index \(i \ge 3\), \(w_i \ge w_{i-1} + w_{i-2}\).

John cannot place all weights on the scale because of the capacity limit \(C\) (where \(1 \le C \le 2^{30}\)). His goal is to choose a subset of weights such that their total mass is as large as possible without exceeding \(C\), so that this sum represents the maximum cow weight that can be measured without damaging the scale.

Your task is to determine this maximum total mass based on the given weights and the capacity \(C\).

inputFormat

The input consists of two lines:

• The first line contains two integers \(N\) and \(C\) separated by a space.
• The second line contains \(N\) integers, representing the masses of the weights in non-decreasing order.

outputFormat

Output a single integer, which is the maximum total mass of a subset of weights that does not exceed \(C\).

sample

3 10
1 3 6

10