暂无测试数据。

题目描述

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

输入

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

输出

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

样例输入

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

样例输出

261

数据范围限制

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

来源

基础篇补充7.7