0-1 Knapsack Problem

You are given a knapsack with a maximum weight capacity \(W\) and \(N\) items. Each item has a weight and a value. Your task is to determine the maximum total value of items that can be put into the knapsack without exceeding the weight capacity. Each item can be selected at most once.

The problem can be formally described as follows:

Given a weight limit \(W\) and a list of \(N\) items where the \(i\)th item has a weight \(w_i\) and a value \(v_i\), find the maximum total value \(V\) such that the sum of weights of the chosen items does not exceed \(W\).

Input Format: The first line contains two integers \(W\) and \(N\). The next \(N\) lines each contain two integers representing the weight and the value of an item.

Output Format: Output a single integer representing the maximum value that can be achieved.

inputFormat

The input is read from stdin and consists of multiple lines. The first line contains two space-separated integers (W) (the weight limit) and (N) (the number of items). Each of the following (N) lines contains two integers: the weight and the value of an item.

outputFormat

The output is written to stdout and should be a single integer representing the maximum total value that can be achieved without exceeding the weight limit (W).## sample

50 3
10 60
20 100
30 120

220