In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of April 14th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]

In this problem you should submit a complete program with the main function, reading with functions such as scanf and printing with functions such as printf.

[PII044] Smelly Cat

Phoebe Buffay is on a mission to create the perfect playlist one that’s just the right length for her mood, without repeating songs. She has a list of available songs (including Smelly Cat, of course), and she wants to obey he following rules:

• The total duration of the play list should not exceed duration D (Phoebe doesn't like to be left halfway through a song)
• The total duration should be as close as possible do duration D (so that she doesn't too long listening to nothing)
• No song can appear more than once in the playlist (she doesn't like to hear the same song two times)

Imagine for instance that Phoebe has the following 9 songs available:

Consider that Phoebe wants a play list with duration D = 1300 seconds. If she starts adding songs while the duration is not is not exceeded, she obtains the following playlist:

• Alternative 1: #01, #02, #03, #04  |  Duration: 202+243+254+502 = 1201 seconds

Phoebe then tried in increasing order of duration, starting with the smallest one, obtaining the following playlist, which is worse than the previous one:

• Alternative 2: #09, #01, #07, #02, #3  |  Duration: 192+202+237+243+254 = 1128 seconds

Phoebe tried many other strategies (such as starting with the longest music) but quickly discovered none of these strategies would always give the best possible solution. In particular, for this case, the best playlist is the following (with only 2 seconds less than the desired duration):

• Alternative 3: #05, #08, #09  |  Duration: 385+721+192 = 1298 seconds

Can you help Phoebe find the best playlist for a general case?

The Problem

Given a duration D and a set of songs (specified by their duration), you have to calculate the duration of the optimal playlist, i.e. the subset of songs such that the sum of their durations is as large as possible and at the same time this sum is less than or equal to D.

Input

The first line of input contains two integers D (the desired playlist duration) and N (the number of songs available).

N lines follow, each one with am integer S_i indicating the duration of the i-th song. It is guaranteed that at least one song as a duration smaller or equal than D.

Output

The output should be a line containing the total duration of the best possible playlist, that is, the choice of a subset of songs that maximizes ∑s_i such that ∑S_i≤D

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1300 9
202
243
254
502
385
942
237
721
192

1298