题目描述

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

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

输入格式

第 1 行：两个正整数，背包最大载重 maxw ，物品总数 n；

第 2 行到第 n+1 行：两个正整数，代表每个物品的重量 $w_i$ 和价值 $p_i$

输出格式

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

样例

10 3
4 5
3 4
6 9

14