暂无测试数据。

题目描述

有个背包可承受重量 \(N\)，
现有 \(T\) 件物品
每件物品重量为 \(W_i\), 价值为 \(V_i\) ,
每件物品只有一个,
这个背包可以装载物品的最大价值是多少?

输入

一行,\(N，T\)，两个数之间用空格隔开。
后面 \(t\) 行,
每行: 重量 \(W_i\),价值 \(V_i\)。

输出

这个背包可以装载物品的最大价值。

样例输入

100 5
77 92
22 22
29 87
50 46
99 90

样例输出

133

数据范围限制

\(N \leq 1000\)，\(T \leq 100\)，\(1 \leq W_i,V_i \leq 100\).

来源

基础篇补充7.6