描述

有一个背包能装的重量$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