Problem2857--背包-二

2857: 背包-二

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

有个背包可承受重量N，现有T件物品，每件物品重量为Wi,价值为Vi ,每件物品的数量是无穷的,这个背包可以装载物品的最大价值是多少?

Input

第一行，两个整数，分别表示N和T，用空格隔开（N≤1000，T≤100）
接下来T行，每行两个整数，分别表示T件物品的重量Wi和价值Vi（1≤Wi,Vi≤100）


Output

一行，表示这个背包可以装载物品的最大价值

Sample Input Copy 

100 5
77 92
22 22
29 87
50 46
99 90

Sample Output Copy 

261

Source/Category

01背包 CCF level5 
[Submit] [Status]