LKS - Large Knapsack


The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Just implement 0/1 Knapsack.

Input

First line contains two integers K and N, where K in the maximum knapsack size and N is the number of items. N lines follow where ith line describes ith item in the form vi and wi where vi is the value and wi is the weight of ith item.

Output

Output a single number - maximum value of knapsack. (All operations and the answer are guaranteed to fit in signed 32-bit integer.)

Time limit changed to 2s on 02.07.11.

Example

Input:
10 3
7 3
8 8
4 6

Output:
11

Constraints

K <= 2000000
N <= 500
Vi <= 10^7
Wi <= 10^7


hide comments
surayans tiwari(http://bit.ly/1EPzcpv): 2014-06-20 12:24:15

heyy i am again again getting wrong ans i tried every possible test case seriously i need help
<snip>

Last edit: 2022-09-27 20:32:14
heatOn: 2014-05-25 04:51:50

vectors are slow. Using vector gave TLE !!
Use normal array for knapsack instead of vectors .

mohit gupta: 2014-04-05 21:24:48

dont know y
bt my solution got acepted yet its giving wrong result in the test case provided here

californiagurl: 2014-03-16 08:12:01

a senior at my colg taught me this optimization,, which is why i'm probably not as excited about getting this right ....i've always solved DP problems with this optimization

innovolt: 2014-03-10 15:05:43

fod and macho ques.....very gud optimiztion thanx to spoj and Shikhar Sharad

CoNtRaDiCtIoN: 2014-01-28 19:47:38

enjoyed a lot upon doing this :)very happy

Luka: 2014-01-26 07:10:14

SIGSEGV !!! :(

Fendy: 2013-12-14 07:55:30

I tried to solve this using top-down knapsack DP, but I can't handle about the memory problem, can someone help me? thanks in advance

SanchitK: 2013-12-13 18:36:39

my code shows segmentation error in spoj.please help
<snip>

Last edit: 2022-09-27 20:33:34
Ouditchya Sinha: 2013-10-23 11:33:14

@Ashish Tilokani : Congratulations!! 2.2M & 0.00s, was it magic? :)

I have already solved this problem, but I would like to learn how you did it. Any hints?


Added by:Ace
Date:2013-06-24
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64