Maximum Total Duration Under Limit

You are given a maximum allowed duration N, an integer representing the number of messages M, and a list of M message durations. Your task is to determine the maximum total duration that can be achieved by selecting a subset of messages such that their combined duration does not exceed N.

This is a subset sum / knapsack problem where you must choose some durations whose sum is as large as possible without exceeding the given limit N. Formally, if you denote the selected durations by a subset S, then you need to maximize

subject to

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains two space-separated integers: N (the maximum allowed total duration) and M (the number of messages).
• The second line contains M space-separated integers representing the durations of the messages.

outputFormat

Output a single integer to standard output (stdout) denoting the maximum total duration that can be achieved without exceeding the limit N.

10 3
4 5 1

10