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
Ashish Tilokani: 2013-10-23 08:27:42

fastest in c and most memory efficient in all!!

Ashish Tilokani: 2013-10-23 08:24:29

the chances of my solution getting accepted was very low!! for some test cases my solution won't work for sure

bigBOSS: 2013-08-27 09:25:07

nice prob....but dont know how to reduce the execution time...:(

Ouditchya Sinha: 2013-08-02 05:18:41

Nice problem! Simple Twist of 0/1 Knapsack. :)

Mostafa 36a2: 2013-07-19 13:27:10

Man ! implementing 0/1 Knapsack is far different than the easy fractional version ...
I took time before notice the difference :p

Last edit: 2013-07-21 01:47:54
karan173: 2013-07-16 09:42:30

wow guys there's a trick!!

Federico Lebrón: 2013-07-10 04:30:57

@Light Yagami: In general, cin and cout incur some overhead over scanf and printf. If the input is large, as it can be here (N lines, N somewhat large), scanf and printf will outperform cin and cout. Part of the slowness can be mitigated by calling cin.sync_with_stdio(false), and same with cout (be aware that C-style IO and C++-style IO will now be out of sync, don't try to use them together, they won't share a buffer or locks), but if you absolutely want the fastest, you can try replacing C++ style IO with C style IO.

technophyle: 2013-07-05 01:01:04

OK now I got AC using int instead of long long since you mentioned that answer is going to fit in signed 32-bit integer.

But still I wonder why using scanf and printf have slightly slow run time than cout and cin on my submission.

Last edit: 2013-07-03 12:55:46
BLANKRK: 2013-07-05 01:01:04

nice one.... :D got AC


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