KNAPSACK  The Knapsack Problem
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
anand__20:
20151018 20:53:26
did it using recursive approach first...got TLE...dp solution got AC in first attempt... 

dedeibel:
20150910 20:46:27
Cannot be done in clojure, time limit is exceeded even by hello world. 

Kamal raj. S. D:
20150903 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:
20150811 22:20:54
Recursive approach gives TLE but dp gives AC _ 

Amanpreet Singh:
20150711 17:26:18
Ac in second attempt. :P


uptoyou:
20150704 10:59:24
AC in one go :)) 

Rishabh Prasad:
20150623 21:32:46
can anyone please the explain the output? 

rohit_dhan:
20150616 14:18:12
First dp... 

nerd:
20150112 18:24:59
my first dp :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150104 20:29:50
Pyramid cluster unavailable for now, all new submission to this problem (and any pyramid problem) rejected :O

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