Maximum Calorie Subset

You are given a target calorie value \(T\) and a list of \(N\) food items with their corresponding calorie values. Your task is to select a subset of these food items such that the total calorie count is as high as possible but does not exceed \(T\). This problem is analogous to the classic 0/1 Knapsack problem.

Input: A target integer \(T\) and a list of integers representing the calorie values of food items.

Output: The maximum sum of selected calorie values that does not exceed \(T\).

Example: For \(T = 750\) and calories = [100, 200, 300, 400, 500], one optimal subset yields a total of 700 calories.

inputFormat

The input is read from standard input (stdin) and consists of three parts:

1. The first line contains an integer \(T\), the target calorie count.
2. The second line contains an integer \(N\), the number of food items.
3. The third line contains \(N\) space-separated integers, each representing the calorie value of a food item.

outputFormat

Output a single integer to standard output (stdout): the maximum possible calorie sum that does not exceed \(T\).

750
5
100 200 300 400 500

700