Sphere Online Judge

SPOJ Problem Set (classical)

97. Party Schedule

Problem code: PARTY


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 0

Sample output:

49 26 48 32

Added by:Patryk Pomykalski
Date:2004-07-01
Time limit:3s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:Swiss Olympiad in Informatics 2004

hide comments
2014-04-19 08:27:55 SHIVAM DUGGAL
i m getting wa espite getting correct output for all test cases on ideone and codeblocks
please check my id.
and reply asap
2014-04-08 16:52:19 Eric Gross
I checked the forums and all the posts for possible test cases, which my code has gotten AC for all of them, but I get WA when submitting. Any idea why?

ID : 11409871
2014-03-31 17:21:03 Anubhav Balodhi ;-D
@Avneesh nice n simple explanation yaar... @Dexter roger that :-)
2014-03-09 05:20:12 Innovolt
AC..........enjoyed much
2014-02-23 21:48:36 Shahed al mamun
wa for problem 4301.Need some critical input
2014-02-14 16:54:32 californiagurl
should we sort with respect to entrance fee first, and then proceed with dp?
2014-02-01 17:25:08 Sudarshan K
Calculation of entrance fee.:) Phew. Now i know what 0-1 Knapsack is. Keep calm and dp.!
2014-01-02 08:25:32 Tushar Goyal
Calculation of Entrance Fee Part ;)
@reggaeguitar thanks for the test case
2013-12-05 21:07:45 prudhvi
base case.... always keep looking....
2013-10-22 23:03:46 reggaeguitar
Check this test case
7 2
6 1
5 1

0 0

your output should be: 5 1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.