说明

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

题目描述

$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≤17000$
• $0＜w_i,c_i≤200000$