题目描述

卢本伟有个好朋友叫做金明。在 $\text{NOIP2006}$ 中，金明已经很高兴了，但是他今天想要让他更开心，因此他会买来很多东西。在金明眼中，所有东西的重要指数都是五五开的，因此他用整数 $1-5$ 来表示一个物品的重要指数，$5$ 是最重要的。而每件物品对金明的价值则是它的价格与重要指数的乘积。为了尽可能让金明高兴，卢本伟得想办法最大化买来物品的总价值。当然，为了防止消费过度而去世，他要保证物品的总价格不大于 $n$。

输入格式

第一行，为 $2$ 个正整数，用一个空格隔开：$n,m$（其中 $n$ 表示总钱数，$m$ 为希望购买物品的个数。）

从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v,p$（其中 $v$ 表示该物品的价格 $v$($1 \le v \le 10000$)，$p$ 表示该物品的重要度($1 \le p \le 5$))。

输出格式

一个整数，表示物品的价格与重要指数乘积的和的最大值。

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

3900

提示

卢本伟买了第 $2$、$3$、$5$ 件物品，总价值为 $400 \times 5+300 \times 5+200 \times 2=3900$，金明十分地哈啤。

答案不超过 $10^9$

数据范围

$1 \le n \le 100000$

$1 \le m \le 100$