LCC '22 Contest 2 S2 - Medicinal Nuts

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

Scribbles the squirrel just got COVID-19 and is feeling very sick. To compensate, they decided to go and grab some medicinal nuts! Each of the N nuts has a medicinal value of v_i, and by eating multiple nuts, you can get a a higher medicinal value of the sum of the nut values. However, Scribbles does not want to overdose on medicine (unlike some other squirrels), so they need to make sure that the total medicinal value does not go above M. Scribbles isn't very good at problem solving, so could you help them find out the maximum medicinal value they can get?

Constraints

1 \le N \le 20

1 \le M \le 10^9

1 \le v_i \le 10^9

Input Specification

The first line will contain two integer N and M, representing the number of medicinal nuts and the largest medicinal intake respectively.

The next line will contain N integers v_i, representing the medicinal value of the i-th nut.

Output Specification

The largest possible sum that is less than or equal to M.

Sample Input 1

4 6
3 2 2 5

Sample Output 1

5

Sample Output Explanation

One way Scribbles can have a value of 5 is by taking 3 and 2. It can be shown that this is the largest value less than or equal to 6.


Comments

There are no comments at the moment.