问题描述

有一个背包能装的重量 $maxw$ (正整数，$0 \le maxw \le 20000$)，同时有 $n$ 件物品($1 \le n \le 100$)，每件物品有一个重量 $w_i$ (正整数)和一个价值 $p_i$ (正整数)。要求从这 $n$ 件物品中任取若干件装入背包内，使背包的物品价值最大。

输入格式

第 $1$ 行：背包最大载重 $maxw$，物品总数 $n$ ； 第 $2$ 行到第 $n+1$ 行：每个物品的重量和价值；

输出格式

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

样例

输入

10 3
4 5
3 4
6 9

输出

14