题目描述
教授要搬家了,需要购置一批新的家具,教授开始做预算,但是他想买的东西太多了,肯定会自己拥有的N元。于是,他把每件物品规定了一个想买程度,分为5等:用整数1~5表示,第5等最想买,而每个物品有一个q值,q值是想买程度和价格的乘积。教授希望在不超过N元(可以等于N元)的前提下,使每件物品的q值总和最大。
请你帮助金明设计一个满足要求的购物单。
输入描述
输入包含多个测试数据。
每个测试数据的第1行,为两个正整数,用一个空格隔开:
N m
(其中N(<=30000)表示总钱数,m(<=25)为希望购买物品的个数。)
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数
v p
(其中v表示该物品的价格(v<=10000),p表示该物品的想买程度(1~5))
输出描述
对于每个测试数据输出一行,其中只含有一个正整数,为q值(<100000000)。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
提示