Shopping List Optimization

Kim Ming is excited because he is about to receive the keys to his new house, which includes a spacious room dedicated just for him. His mom has given him the freedom to decide what items to purchase and how to decorate the room, as long as the total spending does not exceed \(N\) yuan. However, Kim Ming’s wishlist is huge and he is sure that buying everything would exceed the budget.

To handle this, he assigns each potential item an importance rating from 1 to 5 (with 5 being the most important) and has also noted down each item’s price (in integral yuan). Kim Ming now wants to choose a subset of items such that their total cost does not exceed \(N\) yuan and the sum of the product of each item’s price and its importance is maximized. More formally, if the selected items are indexed by \(j_1, j_2, \ldots, j_k\), then you are to maximize:

[ v_{j_1}\times w_{j_1} + v_{j_2}\times w_{j_2} + \ldots + v_{j_k}\times w_{j_k} ]

Your task is to help Kim Ming design an optimal shopping list under his mom’s budget constraint.

inputFormat

The input starts with a line containing two integers \(N\) and \(M\) -- the total budget and the number of available items respectively. This is followed by \(M\) lines, each containing two integers \(v\) and \(w\) where \(v\) is the price of an item and \(w\) (from 1 to 5) is its importance rating.

Constraints:

• \(N\) is a positive integer representing the budget.
• \(M\) is the number of items.
• \(v\) and \(w\) are positive integers with \(w\) in \(\{1, 2, 3, 4, 5\}\).

outputFormat

Output a single integer, the maximum possible sum of \(v_j \times w_j\) for the selected items, such that their total price does not exceed \(N\) yuan.

sample

50 3
20 4
30 5
30 3

230