暂无测试数据。

题目描述

有个背包可承受重量 $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