题目描述

一个旅行者有一个最多能装 $m$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $w_1, w_2, \dots, w_n$，它们的价值分别为 $c_1, c_2, \dots, c_n$，求旅行者能获得最大总价值。

输入格式

第一行包含两个整数 $m, n$，分别表示背包容量和物品数量。

接下来 $n$ 行，每行包含两个整数 $w_i, c_i$，表示每个物品的重量和价值。

输出格式

输出一行一个整数，表示最大总价值。

10 4
2 1
3 3
4 5
7 9

12

数据规模与约定

对于全部的测试点，保证 $0 \leq m \leq 200$, $0 \leq n \leq 30$，并且对于每个物品，$w_i$ 和 $c_i$ 是非负整数。