DWITE Online Computer Programming Contest
November 2008
Problem 4
Big shiny tunes

Having acquired more (totally legitimate) music than a tiny iPod Nano can hold (it's a first generation 2 GB model, so that's plausible) and wanting to load music in full albums only, this has posed quite a challenge for deciding on the playlists. To complicate the matters further, the disk space is shared with other data, so it fluctuates from time to time. This calls for some Computer Science.

The input file DATA4.txt will contain 5 sets of input. The first line is the space available, an integer value 1 <= S <= 100. The second line is an integer N, the number of albums in the library, 1 <= N <= 20. The next N lines describe the albums -- the space required and total utility; both are integer values, separated by a space; 1 <= space, utility <= 1000. Each set is separated by a newline.

The output file OUT4.txt will contain 5 lines of output, each being the sum of the maximum utility that could fit given the associated input.

Note: Each album can appear only once in the playlist, though space-utility values are not guaranteed to be unique.

Sample Input (first three shown):
100
3
90 1000
50 400
50 400

100
3
90 1000
50 600
50 600

100
2
50 500
10 10
		        
Sample Output:
1000
1200
510