Knapsack Problem: Maximum Value

You are given a knapsack with a maximum weight capacity \(W\) and \(N\) items. Each item has a specific weight and value. Your task is to determine the maximum total value of items that can be carried without exceeding the weight limit.

Note: Each item can only be chosen once.

This is a classic 0/1 Knapsack problem where you must design an algorithm to select a subset of items such that the sum of their weights does not exceed \(W\), while the sum of their values is maximized.

inputFormat

The first line contains two integers separated by a space: \(W\) (the maximum weight) and \(N\) (the number of items). The next \(N\) lines each contain two integers: the weight and the value of an item.

Example:

50 3
10 60
20 100
30 120

outputFormat

Output a single integer: the maximum total value that can be carried without exceeding the weight limit \(W\).

50 3
10 60
20 100
30 120

220