You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC184F] Programming Contest

题目描述

给定 $N$ 个数，在数组中选任意个数，使得它们的总和不超过 $T$ 且最大。

输入格式

第一行两个整数 $N,T$ ，第二行 $N$ 个整数 $A_1,A_2,...,A_N$ 。

输出格式

一个整数表示最大和。

样例 #1

样例输入 #1

5 17
2 3 5 7 11

样例输出 #1

17

样例 #2

样例输入 #2

6 100
1 2 7 5 8 10

样例输出 #2

33

样例 #3

样例输入 #3

6 100
101 102 103 104 105 106

样例输出 #3

0

样例 #4

样例输入 #4

7 273599681
6706927 91566569 89131517 71069699 75200339 98298649 92857057

样例输出 #4

273555143

数据范围

• $1\ \le\ N\ \le\ 40$
• $1\ \le\ T\ \le\ 10^9$
• $1\ \le\ A_i\ \le\ 10^9$

样例解释 1

选 $2+3+5+7=17$ 。

样例解释 2

全选。

样例解释 3

没得选。

样例解释 4

选第 $2,3,7$ 个，答案是 $273555143$ 。