该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

战士凯特需要为他的小队配备战斗装备。军械库给了他 $N$ 枚金币的预算，供他购买 $m$ 件不同的装备。

每件装备有两个参数：

• 装备价格：需要花费的金币数

• 效能等级：从 $1$ 到 $5$ 的整数，$5$ 级代表最高战斗效能

小队的整体战力提升等于所有选中装备的 价格 $×$ 效能等级 的总和。

现在给定每件装备的价格和效能等级，请你帮助凯特在不超过预算的情况下，选择装备组合，使得最终的战力提升最大。

数学描述：

设第 $j$ 件装备的价格为 $v_j$，效能等级为 $w_j$，共选中 $k$ 件装备，编号依次为 $j_1, j_2, ..., j_k$，则战力提升总和为： $v_{j_1} × w_{j_1} + v_{j_2} × w_{j_2} + ... + v_{j_k} × w_{j_k}$

输入格式

第一行是两个正整数 $n, m（n < 3×10^4, m < 25）$，其中 $n$ 表示总金币数，$m$ 表示装备数量。

接下来的 $m$ 行，每行给出两个非负整数 $v, p$（其中 $v$ 表示该装备价格，$v ≤ 10^4$，$p$ 表示该装备的效能等级，$1 ≤ p ≤ 5$）。

输出格式

一个正整数，表示不超过预算的战力提升的最大值（数据保证结果 $< 10^8$）。

样例

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

3900

样例解释

对于第一个样例

选择 400（效能5）、300（效能5）、200（效能2）三件装备： 总花费 400+300+200 = 900 ≤ 1000， 战力提升 400×5 + 300×5 + 200×2 = 2000 + 1500 + 400 = 3900。