0/1 Knapsack Problem

You are given a duffel bag which can hold a maximum weight of W and a list of items. Each item has a value and a weight, represented as a pair \( (v_i, w_i) \). Your task is to determine the maximum total value you can achieve by selecting items such that their total weight does not exceed \( W \). Each item can be selected at most once.

The problem can be formulated as follows:

Let \( dp(i, j) \) be the maximum value that can be achieved using the first \( i \) items with a weight limit of \( j \). Then, the recurrence is given by:

\[ dp(i, j) = \begin{cases} dp(i-1, j) & \text{if } w_i > j, \\ \max\{ dp(i-1, j), dp(i-1, j-w_i)+v_i \} & \text{if } w_i \leq j. \end{cases} \]

Your goal is to compute dp(n, W) given \( n \) items.

inputFormat

The input is given through stdin and consists of:

1. A single integer \( W \) representing the maximum weight limit of the duffel bag.
2. A single integer \( n \) representing the number of items available.
3. \( n \) lines follow, each containing two integers: value and weight of an item.

All integers are separated by spaces or newlines.

outputFormat

Output a single integer representing the maximum value that can be achieved without exceeding the weight limit. The output should be written to stdout.

## sample

50
3
60 10
100 20
120 30

220

</p>