Migrated from Lutece 2658 考试破防周

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

不知不觉又到了一学期一度的考试破防周 orz。

坤坤期末要考 $N$ 门课，然而他却只剩 $T$ 天预习它们。

凭借他超强的摸鱼能力，他已经知道了预习第 $i$ 门课需要 $t_i$ 天。

在未来的 $T$ 天内，他想从 $N$ 门中选择 $0$ 门或多门预习。注意：因为坤坤太菜了，所以不能同时预习多门课。并且预习方案中有的课会预习不完，则坤坤不会采取该预习方案。

然而坤坤不希望被别人嘲讽摸鱼，所以想知道自己最多可以花多少天在预习上。

Input

所有的输入均为整数。

第一行输入是用一个空格隔开的 $N$ 和 $T$。其中 $1\leq N\leq 40, \, 1\leq T \leq 10^9$，它们分别代表坤坤要考的总课数和坤坤可用于预习的最大天数。

第二行输入是 $N$ 个正整数 $A_i$，它们表示第 $i$ 门课所需的预习时间。其中 $1\leq i \leq N ,\, 1\leq A_i \leq 10^9$。

Output

输出一个整数，表示坤坤的最大预习天数。

Samples

5 17
2 3 5 7 11

17

6 100
1 2 7 5 8 10

33

Note

样例 1 说明：选择第 $1,2,3,4$ 门课预习，共花 $17$ 天。 样例 2 说明：全预习，共花 $33$ 天。

Resources

2021 UESTC ICPC Training for String and Search Algorithm