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

Background

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

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

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

Format

Input

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

从第2行到第m+1行，第j行给出了编号为j-1的奖品的基本数据，每行有2个非负整数 v, p（其中v表示该奖品的价格(v ≤ 10000)，p表示该奖品的受欢迎程度(1 ≤ p ≤ 5)）。

Output

1个正整数，为不超过预算金额的奖品的价格与受欢迎程度乘积的总和的最大值（<100000000）。

Samples

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

3900

Limitation

1s, 1024KiB for each test case.