輸入格式
每組測資第一行包含兩個正整數,分別代表背包大小 $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