题目描述

一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $N$ 件物品，第 $i$ 件物品的重量为 $W_i$ ，价值为 $C_i$ ，求旅行者能获得最大总价值。

输入格式

第一行包含两个整数 $M$ 和 $N$

接下来 $N$ 行：每行两个整数 $W_i,C_i$，表示每个物品的重量和价值。

$M,N≤1000$

输出格式

仅一行，一个数，表示最大总价值。

样例：

10 4
2 1
3 3
4 5
7 9

12