Login Register

Problem A: 0-1背包

Time Limit: 1 Sec Memory Limit: 128 MB
Submit Solution

Description

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是w1,w2,w3...wn，它们的价值分别是c1,c2,c3...cn，求旅行者能获得最大总价值。

Input

两个整数M(背包容量)，N(物品数量)
接下来N行，每行两个整数wi,ci，表示重量和价值。

Output

最大总价值

Sample Input

10 4
2 1
3 3
4 5
7 9

Sample Output

12

HINT

M<=200,  N<=30