Xing Yu loves food. However, since he is overweight, his parents make sure that the number of calories consumed is not more than the number of calories he intakes, so as to make sure he loses weight over time. Xing Yu wants to consume as many calories as possible every day. Given the number of calories each food will give and his calorie limit, find the maximum number of calories he can intake.
Input Specification
The amount of calories he can consume (), followed by the number of types of food he can consume ().
The next few numbers are the number of calories each food will give him. Do note that Xing Yu is not allowed to consume any food twice.
Output Specification
The maximum number of calories he can consume. This must be less than the calorie limit, and may not be equal to the calorie limit.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
Sample Input
12 5
3 4 5 6 13
Sample Output
11
Explanation
He can consume the one with 5 and the one with 6 calories. He may not consume 3, 4, 5 since it will result in 12, which is equal to the calorie limit which is not allowed.
Comments