题目描述

社团有 $V$ 元预算，要采购 $n$ 件物品。第 $i$ 件物品价格 $c_i$ 元，买下它能带来 $v_i$ 的满意度。

每件物品最多买一次。求在总花费不超过 $V$ 的前提下，能获得的最大满意度。

输入格式

第一行两个整数 $V, n$（$1 \le V \le 10^5$，$1 \le n \le 100$）。

接下来 $n$ 行，每行两个整数 $c_i, v_i$（$1 \le c_i \le V$，$1 \le v_i \le 10^4$）。

输出格式

一个整数，表示最大满意度。

样例 #1

10 4
5 10
4 40
6 30
3 50

90

买第 2 件和第 4 件，花费 $4+3=7$，满意度 $40+50=90$。

提示

对于 50% 的数据，$V \le 1000$；对于 100% 的数据，$V \le 10^5$。