KNAPSACK - The Knapsack Problem

no tags 

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

hide comments
Nipun: 2016-02-09 20:32:41

My first dp, you f***rs!! I am the king of the world... yayayayay....

sudip_95: 2016-01-28 07:23:20

just use memoization using recursive top down approach. AC at first attempt! :D

theph0enix: 2016-01-24 12:45:10

TLE with python3.4 and dp with both top-down/bottom-up apprach.. :(

Last edit: 2016-02-19 11:16:33
Alex-ander007: 2016-01-22 18:21:54

Got TLE for top down. Any idea why??

Junaid: 2015-12-16 08:15:27

DP rocks.....:p

shirayuki_rin: 2015-12-04 09:07:28

Does anyone know why I get WA? My submission ID is 15775271. Please help, as the forum is not available.

anand__20: 2015-10-18 20:53:26

did it using recursive approach first...got TLE...dp solution got AC in first attempt...

dedeibel: 2015-09-10 20:46:27

Cannot be done in clojure, time limit is exceeded even by hello world.

Kamal raj. S. D: 2015-09-03 14:09:53

Its shows TLE in spoj and success with 0.01 time in ideone. I dont know wats the problem. i used dp solution and python as the language.

xceptor: 2015-08-11 22:20:54

Recursive approach gives TLE but dp gives AC -_-


Added by:Nikola P Borisov
Date:2008-11-10
Time limit:0.240s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS NODEJS PERL 6 VB.net