Aladdin's knapsack#1661
Upon entering the treasure cave, Aladdin chose not to take the old, blackened lamp. Instead, he began filling his backpack with gold coins and precious gems. Of course, he wanted to take everything, but his backpack had a limited carrying capacity and could not withstand excessive weight.
Many times, he removed some items and replaced them with others, striving to maximize the total value in his backpack.
The task is to determine the maximum value of the cargo that Aladdin can carry.
Assume that the cave contains different types of items, with an unlimited number of each type available. The backpack can carry at most weight. Each item of type has weight w_i and value v_i (i = 1, 2, \ldots, n).
The first line contains two positive integers and (1 \le s \le 250, 1 \le n \le 35) — the maximum weight the backpack can carry and the number of item types.
The following lines each contain two integers w_i and v_i (1 \le w_i \le 250, 1 \le v_i \le 250) — the weight and value of an item of type .
Print the maximum total value of the cargo that can be carried without exceeding the weight limit .
Example 1