PARTY  Party Schedule
You just received another bill which you cannot pay because you lack the money.
Unfortunately, this is not the first time to happen, and now you decide to investigate the cause of your constant monetary shortness. The reason is quite obvious: the lion's share of your money routinely disappears at the entrance of party localities.
You make up your mind to solve the problem where it arises, namely at the parties themselves. You introduce a limit for your party budget and try to have the most possible fun with regard to this limit.
You inquire beforehand about the entrance fee to each party and estimate how much fun you might have there. The list is readily compiled, but how do you actually pick the parties that give you the most fun and do not exceed your budget?
Write a program which finds this optimal set of parties that offer the most fun. Keep in mind that your budget need not necessarily be reached exactly. Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.
Input
The first line of the input specifies your party budget and the number n of parties.
The following n lines contain two numbers each. The first number indicates the entrance fee of each party. Parties cost between 5 and 25 francs. The second number indicates the amount of fun of each party, given as an integer number ranging from 0 to 10.
The budget will not exceed 500 and there will be at most 100 parties. All numbers are separated by a single space.
There are many test cases. Input ends with 0 0.
Output
For each test case your program must output the sum of the entrance fees and the sum of all fun values of an optimal solution. Both numbers must be separated by a single space.
Example
Sample input:
50 10 12 3 15 8 16 9 16 6 10 2 21 9 18 4 12 4 17 8 18 9 50 10 13 8 19 10 16 8 12 9 10 2 12 8 13 5 15 5 11 7 16 2 0 0Sample output:
49 26 48 32
Added by:  Patryk Pomykalski 
Date:  20040701 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: SCM chicken 
Resource:  Swiss Olympiad in Informatics 2004 
hide comments
Ankit:
20150322 10:13:25
Awesome Problem. AC in 1 Go :)


jugalsahu10:
20150316 18:41:48
Realy very nice problem..... 

anando_du:
20150311 16:17:43
aaah ... AC in 2nd go !!! this problem is damn good !!! remember about maximum fun with minimum cost ! so if you get same fun with cost c1 and c2 where c1 < c2 then the ans will be c1 ..... you must find minimum c1 ? :P i meant something more interesting with the word "find" > ? ? :P :P think :P


Deepak Singh Tomar:
20150308 21:04:10
tag> 01 knapsack dp 

xxbloodysantaxx:
20150301 16:05:35
We do not need that extra loop outside that n*sum loop!! Although it doesn't change the complexity 

jobanpreet singh:
20150128 09:20:15
Got WAs in C and NZECs in java just because i didnot read an empty line between two test cases. :(


Manoj Kumar Regar:
20150123 16:38:11
max fun ... min entrance fee 

rccroshan1:
20150122 17:32:47
Am I the only one who has done it using Subset Sum..


deerishi:
20150119 10:51:08
Awesome question!! 

Vishesh Raimugia:
20141223 15:22:13
2nd dp, thanks @Abhishek I was stuck but I found the test case 