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

输入格式

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

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

输出格式

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

样例

样例输入

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

样例输出

133

数据范围与提示

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