Happy Jinming

Problem Background

Special for beginners, ^_^

Problem Description

Jinming is very happy today: his family's newly bought house is about to get its keys, and the new house has a large room that is exclusively his. What makes him even happier is that yesterday his mother said to him: "For the items your room needs and how to arrange them, you decide — as long as it doesn't exceed $N$ yuan." Early this morning Jinming started budgeting, but he wants to buy too many things and will surely exceed the $N$ yuan limit set by his mother. So he assigns an importance to each item, in 5 levels represented by integers 1~5, where level 5 is the most important. He also looked up each item's price online (all integer yuan). He wants, without exceeding $N$ yuan (it may equal $N$ yuan), to maximize the sum of the product of each item's price and its importance.

Let the $j$-th item have price $v[j]$ and importance $w[j]$. If $k$ items are selected, numbered $j_1, j_2, \dots, j_k$ in order, then the desired total is:

$v[j_1]*w[j_1]+v[j_2]*w[j_2]+\dots +v[j_k]*w[j_k]$. (where * means multiplication)

Please help Jinming design a shopping list that satisfies the requirement.

Input Format

The first line contains two positive integers separated by a space:

$N\ m$

(where $N\ (<30000)$ is the total budget, and $m\ (<25)$ is the number of items to buy.)

From the 2nd line to the $(m+1)$-th line, the $j$-th line gives the basic data of item numbered $j-1$, with $2$ non-negative integers per line:

$v\ p$

(where $v$ is the item's price ($v\le 10000$), and $p$ is its importance ($1\sim 5$).)

Output Format

Output a single positive integer — the maximum possible sum of (price × importance) for items whose total price does not exceed the budget ($<100,000,000$).

Sample Input

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

Sample Output

3900

Constraints

1 second, 1024 KiB for each test case.