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 nuts has a medicinal value of , 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 . Scribbles isn't very good at problem solving, so could you help them find out the maximum medicinal value they can get?
Constraints
Input Specification
The first line will contain two integer and , representing the number of medicinal nuts and the largest medicinal intake respectively.
The next line will contain integers , representing the medicinal value of the -th nut.
Output Specification
The largest possible sum that is less than or equal to .
Sample Input 1
4 6
3 2 2 5
Sample Output 1
5
Sample Output Explanation
One way Scribbles can have a value of is by taking and . It can be shown that this is the largest value less than or equal to .
Comments