DWITE Online Computer Programming Contest, December 2007, Problem 3
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 to (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 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, . Followed by lines in the form title rating space. The title will be a unique single string (no spaces). Rating is an integer to . Space is an integer, . Followed by the next data set.
The output 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