You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。 更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。 今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。 于是，他把每件物品规定了一个重要度，分为5等：用整数1 ~5 表示，第5 等最重要。 他还从因特网上查到了每件物品的价格（都是整数元）。 他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为$v[j]$ ，重要度为$w[j]$ ，共选中了$k$ 件物品，编号依次为$j1 ，j2 ，……，jk ，$则所求的总和为：

$v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]$ 。（其中∗ 为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式

输入的第1 行，为两个正整数，

N m （其中N<30000 ）表示总钱数，m<25 ）为希望购买物品的个数。）

从第2 行到第m+1 行，第$j$ 行给出了编号为$j−1$ 的物品的基本数据，每行有2 个非负整数

$v$ $p$ （其中v 表示该物品的价格($v<=10000$) ，p表示该物品的重要度(1 ~5) )

输出格式

输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值$（<100000000 ）$。

样例数据

input

10 5

8 2

4 5

3 5

4 3

2 2

output

39

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$