Problem 22409 --01背包

22409: 01背包

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 73  Solved: 36
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

一个旅行者有一个最多能用M公斤的背包,现在有N件物品,
它们的重量分别是W1,W2,...,Wn,
它们的价值分别为P1,P2,...,Pn.
若每种物品只有一件求旅行者能获得最大总价值。

Input

M,N
W1,P1
W2,P2
......

Output

最大总价值。

Sample Input

10 4
2 1
3 3
4 5
7 9

Sample Output

12

HINT

Source

[Submit][Status]