说明

本题和本OJ730题目叙述一样，但是数据范围不一样

题目描述

$01$背包问题是学习背包问题的基础，要求必须掌握。

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

若每一种物品只有一件，求旅行者能获得的最大总价值。

输入格式

第 $1$ 行：两个整数 $m,n$，表示背包容量和物品数量；

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

输出格式

一个数据，表示最大总价值

样例

10 4
2 1
3 3
4 5
7 9

12

数据范围

$0＜m,n≤200$

$0＜w_i,c_i≤200000$