0/1 Knapsack Problem

You are given a weight limit \(W\) and a list of \(N\) items, where each item is described by its value \(v\) and weight \(w\). Your task is to determine the maximum total value that can be accumulated by selecting a subset of these items without exceeding the weight limit \(W\).

Input Format:

• The first line contains an integer \(W\), the weight limit.
• The second line contains an integer \(N\), the number of items.
• The next \(N\) lines each contain two integers separated by a space: the value \(v\) and the weight \(w\) of an item.

Output Format:

• Output a single integer, the maximum total value that can be achieved under the given weight constraint.

Example:

Input:
50
3
60 10
100 20
120 30
Output:
220

</p>

inputFormat

The input is read from standard input (stdin) and has the following structure:

• \(W\): the first line is an integer representing the weight limit.
• \(N\): the second line is an integer representing the number of items.
• Next \(N\) lines: each line contains two space-separated integers denoting the value and weight of an item respectively.

outputFormat

Output to standard output (stdout) a single integer which is the maximum total value that can be obtained without exceeding the weight limit \(W\).

## sample

50
3
60 10
100 20
120 30

220