Description

There are n types of items, each with a weight and a value. However, the quantity of each item is unlimited. Given a backpack with a maximum load capacity of M, select any number of items (the same item can be selected multiple times) such that the total weight is less than or equal to M, while the total value is maximized.

Input Format

• The first line: two integers, M (backpack capacity, M ≤ 200) and N (number of items, N ≤ 30).
• Lines 2 to N+1: each line contains two integers, Wi and Ci, representing the weight and value of each item, respectively.

Output Format

A single line containing the maximum total value.

10 4
2 1
3 3
4 5
7 9

max=12