题目描述

晨瑞今天很开心，因为他的母亲大人终于答应他让他DIY一套属于自己的计算机。 但也不是无上限的选购DIY,总花费不能超过$N$元钱.晨瑞想买的东西非常多，为了尽可能让计算机符合自己的需求，他把需要购买的物品做了分级，分别是1-5级，用整数1-5来表示，他还查询到了每件物品的价格都是整数，晨瑞希望在不超预算的情况下，使每件物品的价格与等级的乘积的总和最大。

设第$j$件物品的价格为$v[j]$，等级为$w[j]$，共选中了$k$件物品，编号依次为$j_1,j_2,…,j_k$，则所求的总和为：

$v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]$。

请大家务必帮助晨瑞设计一个满足要求的DIY购买计划清单。

输入格式

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

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

输出格式

$1$个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值$(<100000000)$。

样例 #1

样例输入 #1

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

样例输出 #1

3900

提示

晨瑞：在线等方案很急！