版权声明

本题版权归 所有。

题目来源暂未公开。

题目描述

现有 $n$ 包巨大的零食，其中第 $i$ 包零食的体积和质量均为 $a_i$。

你有一个大小为 $w$ 的背包，问其中最多能装得下多重的零食？

输入格式

本题有多组数据。

对于每组数据：

第一行两个正整数 $n, w\ (1 \le n \le 40, 1 \le w \le 10^{18})$。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n\ (1 \le a_i \le w)$。

输入以 EOF 结束。

保证单个测试点内所有 $\left( \sqrt{2} \right) ^n$ 的和不大于 $2^{20}$，且输入的数字个数不超过 $2.5 \times 10^5$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例

5 10
5 6 7 8 9
5 20
1 4 5 7 18
10 100
11 22 33 44 55 66 77 88 99 100
10 3333
663 737 842 672 1000 646 856 685 1116 776

9
19
100
3329