20005. 0/1 Knapsack Problem (Design Strategies for Computer Algorithms)

輸入格式

每組測資第一行包含兩個正整數，分別代表背包大小 $M$ ($\leq 5×10^6$) 和物品個數 $N$ ($\leq 1000$)，下一行開始每行包含兩個正整數，分別代表物品價值 $P_i$ ($\leq 10^5$)和物品重量 $W_i$ ($ \leq 10^5$)。

輸出格式

對於每組測資，請輸出最大收益。

範例輸入 1

50 7
70 31
20 10
39 20
37 19
7 4
5 3
10 6

範例輸出 1

107

範例輸入 2

170 7
442 41
525 50
511 49
593 59
546 55
564 57
617 60

範例輸出 2

1735