{"raw_statement":[{"iden":"problem statement","content":"Takahashi will participate in a programming contest, which lasts for $T$ minutes and presents $N$ problems.  \nWith his extrasensory perception, he already knows that it will take $A_i$ minutes to solve the $i$\\-th problem.  \nHe will choose zero or more problems to solve from the $N$ problems so that it takes him no longer than $T$ minutes in total to solve them.  \nFind the longest possible time it takes him to solve his choice of problems."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\le N \\le 40$\n*   $1 \\le T \\le 10^9$\n*   $1 \\le A_i \\le 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $T$\n$A_1$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"5 17\n2 3 5 7 11"},{"iden":"sample output 1","content":"17\n\nIf he chooses the $1$\\-st, $2$\\-nd, $3$\\-rd, and $4$\\-th problems, it takes him $2+3+5+7=17$ minutes in total to solve them, which is the longest possible time not exceeding $T=17$ minutes."},{"iden":"sample input 2","content":"6 100\n1 2 7 5 8 10"},{"iden":"sample output 2","content":"33\n\nIt is optimal to solve all the problems."},{"iden":"sample input 3","content":"6 100\n101 102 103 104 105 106"},{"iden":"sample output 3","content":"0\n\nHe cannot solve any of the problems."},{"iden":"sample input 4","content":"7 273599681\n6706927 91566569 89131517 71069699 75200339 98298649 92857057"},{"iden":"sample output 4","content":"273555143\n\nIf he chooses the $2$\\-nd, $3$\\-rd, and $7$\\-th problems, it takes him $273555143$ minutes in total to solve them."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}