DWITE Online Computer Programming Contest, November 2008, Problem 4

Having acquired more (totally legitimate) music than a tiny iPod Nano (it's a first generation, 2GB model, so that's plausible) can hold, and wanting to load music in full albums only, has posed quite a challenge for deciding on the playlists. To complicate 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 will contain 5 sets of input. First line is the space available; an integer value ~1 \le S \le 100~. Second line is an integer ~N~, the number of albums in the library; ~1 \le N \le 20~. The next ~N~ lines describe albums – space required and total utility; both integer values, separated by space; ~1 \le space, utility \le 1000~. Each set is separated by a newline.

The output will contain 5 lines of output, each a sum of 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

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

Problem Resource: DWITE