Description

Jinming is very happy today because his family is about to receive the keys to their new home, which has a spacious room just for him. What makes him even happier is that his mom told him yesterday: “You decide which items to buy and how to furnish your room, as long as the total cost does not exceed $N$ yuan.” Early this morning, Jinming started making a budget, but there are too many things he wants to buy, so the total will definitely exceed the limit $N$. Therefore, he assigns an importance level to each item, divided into 5 levels, represented by integers 1–5, with level 5 being the most important. He also found the price of each item on the Internet (all in integer yuan). He hopes to maximize the sum of price times importance for the selected items, under the constraint that the total cost does not exceed $N$ yuan (it may be equal to $N$ yuan).

Let the price of item $j$ be $v_j$ and its importance be $w_j$. If $k$ items are selected with indices $j_1, j_2, \dots, j_k$, then the desired total is:

$$v_{j_1} \times w_{j_1} + v_{j_2} \times w_{j_2} + \cdots + v_{j_k} \times w_{j_k}.$$

Please help Jinming design a shopping list that meets the requirements.

Input Format

The first line contains $2$ positive integers separated by a space: $n, m$ ($n < 30000, m < 25$), where $n$ is the total amount of money and $m$ is the number of items.

From line $2$ to line $m+1$, the $i$-th of these lines (corresponding to item $i$) contains two non-negative integers $v, p$, where $v$ is the price ($v \le 10000$) and $p$ is the importance ($1 \le p \le 5$).

Output Format

Output $1$ positive integer: the maximum possible value of the sum of price times importance for the selected items without exceeding the total amount of money (this value is $< 100000000$).

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

3900

Hint

NOIP 2006 Junior, Problem 2.

Translated by ChatGPT 5