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

题目描述

学校即将举办运动会，体育老师需要为获奖学生采购奖品。学校拨款的预算总额为N元。体育老师列出了m种候选奖品，每种奖品都有其价格和受欢迎程度（分为1-5级，第5级最受欢迎）。老师希望在不超过预算的前提下，选择一些奖品，使得这些奖品的价格与受欢迎程度的乘积总和最大。

设第j件奖品的价格为vj，受欢迎程度为wj，共选中了k件奖品，编号依次为j₁, j₂, ..., jₖ，则所求的总和为： vj₁ × wj₁ + vj₂ × wj₂ + ... + vjₖ × wjₖ

请你帮助体育老师设计一个满足要求的采购方案。

输入格式

第一行：两个正整数 n, m（n < 30000, m < 25） 其中 n 表示总预算金额，m 为候选奖品的个数。

接下来m行，每行两个整数：价格v和受欢迎程度w

输出格式

一个整数，表示最大的乘积总和

样例

样例 1

输入 # 1

100 3
30 5
20 3
50 4

输出 # 1

130