HCI '16 - Foodie

View as PDF

Submit solution

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

Authors:
Problem type

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 (C), followed by the number of types of food he can consume (N).

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:

0 \le C \le 1\,000\,000

Subtask 1 [20%]

1 \le N \le 20

Subtask 2 [80%]

1 \le N \le 1\,000

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

There are no comments at the moment.