There's a library full of legally purchased music and a shiny new mp3 player that requires to be filled with the best possible playlist. Every song comes with a rating from 0 to 5 (inclusive) and takes up a certain amount of space. The best playlist is defined as the one with the highest total of rating points, that still fits into the allowable space.

The input file DATA3.txt will contain five data sets. The first line will contain the space available in the player, a positive integer. The second line will specify the size of the music library, 1 <= N <= 100. Followed by N lines in the form title rating space. The title will be a unique single string (no spaces). Rating is an integer 0 to 5. Space is an integer, 1 <= S <= 30000. Followed by the next data set.

The output file OUT3.txt will contain five lines, each containing an integer -- a max sum of ratings that can fit on the player.

100
6
song_one 5 25
song_two 5 25
song_three 5 51
song_four 4 50
song_five 3 25
song_six 3 25
        

16