说明

有一个背包能装的重量$maxw$，同时有$n$件物品，每件物品有一个重量$w_i$(正整数)和一个价值$p_i$(正整数)。

要求从这$n$件物品中任取若干件装入背包内，使背包的物品价值最大。

输入格式

第1行：背包最大载重$maxw$，物品总数$n$

第2行到第$n$+1行：每个物品的重量和价值

输出格式

一个数字即背包内物品最大价值

样例

10 3
4 5
3 4
6 9

14

数据范围

• $0≤n≤100$
• $0≤maxw≤20000，maxw是正整数$