Sphere Online Judge

SPOJ Problem Set (tutorial)

3321. The Knapsack Problem

Problem code: KNAPSACK


The famous knapsack problem. You are packing for a vacation on the sea side and you are going to carry only one bag with capacity S (1 <= S <= 2000). You also have N (1<= N <= 2000) items that you might want to take with you to the sea side. Unfortunately you can not fit all of them in the knapsack so you will have to choose. For each item you are given its size and its value. You want to maximize the total value of all the items you are going to bring. What is this maximum total value?

Input

On the first line you are given S and N. N lines follow with two integers on each line describing one of your items. The first number is the size of the item and the next is the value of the item.

Output

You should output a single integer on one like - the total maximum value from the best choice of items for your trip.

Example

Input:
4 5
1 8
2 4
3 0
2 5
2 3


Output:
13

Added by:Nikola P Borisov
Date:2008-11-10
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS NODEJS PERL 6

hide comments
2014-06-25 23:05:33 WA/TLE
first DP @2:36a.m :D
2014-05-31 13:53:37 Achut Nandam
getting TLE in testcase 5 Python2?

Last edit: 2014-05-31 18:53:08
2014-01-27 10:03:19 Ahed AL-Rashaida
this is easy problem to solve in JAVA
2013-12-06 18:40:41 Baratheraja R N
simliar problem: WACHOVIA
2013-09-13 16:39:47 Rishabh Sharma
Very basic problem of DP!
All beginners must try this! :)
2013-08-24 17:05:00 Micheal Scofield
easy knapsack dp :D
2013-08-15 16:38:04 @looser@
good for KNAPSACK algo :)
2013-06-04 14:13:49 Viraj Shah
can someone give me more test cases ? Thanks
2013-03-12 16:38:30 Ouditchya Sinha
Great problem for beginners like me... :)
2011-11-13 07:12:18 manish sharma
an easy one
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.