有$N$种物品和一个容量为$V$的背包。每种物品均有无穷多件，第$i$种物品所占空间是$c_i$，价值是$w_i$。求解将哪些物品装入背包可使价值总和最大

输入格式

第一行为两个整数$V,N$($0 \leq V \leq 1000,0 \lt N \leq 100$)表示背包的容量和物品数量

接下来$N$行，每行有两个整数$C，W$，($0 \lt C \leq 1000，0 \lt V \leq 100$)表示每种物品的所占空间和价值

输出格式

一个整数，表示最大的价值总和

样例

样例输入

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

样例输出

261

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$32767\mathrm{KB}$