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.


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.


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.


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

hide comments
sonali9696: 2016-06-11 12:05:11

It showed that my file size is too large to submit when i used local array for each test case but passed on using global dp array. Weird??

sanjay: 2016-05-28 14:09:44

0/1 knapsack with binary searching the answer .Very good one. Awesome question.Thanks to the author.

sahilagg06: 2016-05-22 14:23:18

Don't read knapsack problem, try to think yourself. Of course, later we can always :)

hardik_iitr: 2016-05-19 05:08:57

4 WA's for using short instead of int. A really basic problem for DP. Must do! :)

shivang_bansal: 2016-05-01 14:33:46

Wrote the 1st code in 10 minutes and got a WA
Realised it is asking for "Minimum Entrance fee"

Hint : For MInimum Entrance fee = ask urself this question - Given a amount of fun, would u like to pay lesser money than the total money u had (as long as u dont make a buyoff with fun) !

Akshay Aradhya: 2016-04-26 18:14:15

OMG I feel so stupid

I was using :
int DP[501][101];

instead of :
int DP[101][501];

rayhan50001: 2016-04-23 20:27:18

More fun, less money--> Add it,, then you will get answer... AC in first Go.

abhivenkiabhi: 2016-04-21 19:18:20

very good question to get started with knapsack

Arpan Mukherjee: 2016-04-12 23:59:46

No need of backtracking,just print the dp table,you'll get the logic. simple 0/1 knapsack.

arundeepak: 2016-04-07 12:42:01

A problem is only difficult until it is solved.
A tweak after classical knapsack is all you need to solve this problem. :)

Added by:Patryk Pomykalski
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Swiss Olympiad in Informatics 2004