Knapsack Problem

In this problem, you are given a knapsack with a weight capacity (W) and (n) items, where each item is characterized by its weight and value. Your task is to select a subset of these items such that the total weight does not exceed (W) and the total value is maximized.

Constraints:

• (1 \le W \le 10000)
• (0 \le n \le 300)
• For each item, (1 \le w_i, v_i \le 1000)

This is a standard 0/1 knapsack problem. When (n = 0), the maximum achievable value is 0. Note that an item can either be taken or left; partial selection is not allowed.

inputFormat

The input is given from standard input (stdin) and consists of:

• A line containing two integers (W) and (n), where (W) is the maximum weight capacity and (n) is the number of items.
• (n) lines follow, each containing two integers representing the weight and the value of each item.

Alternatively, all numbers can be provided in a single line separated by whitespace.

outputFormat

Output the maximum total value that can be achieved without exceeding the knapsack's weight limit. The result should be printed to standard output (stdout).## sample

50 3 10 60 20 100 30 120

220