题目描述

小明搬进了新家，妈妈给了他一笔预算——不超过 $N$ 元，让他自己决定购买哪些物品来布置房间。

小明把每件商品按重要程度分为 $1$ 到 $5$ 共五个等级（$5$ 最重要），并查到了每件商品的价格（均为整数元）。他希望在预算范围内，使所选商品的「价格 $\times$ 重要度」之和最大。

设选中了 $k$ 件商品，编号依次为 $j_1, j_2, \ldots, j_k$，则目标值为：

$$v_{j_1} \times w_{j_1} + v_{j_2} \times w_{j_2} + \cdots + v_{j_k} \times w_{j_k}$$

其中 $v_j$ 为第 $j$ 件商品的价格，$w_j$ 为其重要度。请你帮小明选出一个最优方案。

输入格式

第一行两个正整数 $n, m$（$n \lt 3 \times 10^4$，$m \lt 25$），分别表示总预算和商品数量。

接下来 $m$ 行，第 $j$ 行两个整数 $v, p$，表示第 $j$ 件商品的价格（$v \le 10^4$）和重要度（$1 \le p \le 5$）。

输出格式

输出一个正整数，表示在不超过总预算的前提下，商品价格与重要度乘积之和的最大值（保证结果 $\lt 10^8$）。

样例

1000 5
800 2
400 5
300 5
400 3
200 2

3900