0/1 Knapsack Problem: Maximizing Carried Value

You are given a knapsack with a maximum weight capacity of \(W\) and \(n\) items. Each item is characterized by its weight and value. Your task is to determine the maximum total value you can achieve by selecting a subset of the items such that the total weight does not exceed \(W\).

This is a classical 0/1 Knapsack problem where each item can be taken at most once. The standard dynamic programming approach can be used to solve this problem by maintaining a \(dp\) table where \(dp[w]\) represents the maximum value that can be achieved with a knapsack capacity of \(w\).

Input Format: The first line of input consists of two space-separated integers \(W\) (the maximum weight capacity) and \(n\) (the number of items). This is followed by \(n\) lines, each containing two space-separated integers representing the weight and value of an item.

Output Format: Print a single integer representing the maximum total value achievable without exceeding the capacity \(W\).

inputFormat

The input is read from stdin and is in the following format:

W n
w1 v1
w2 v2
... 
wn vn

Where:

• W is the maximum weight capacity of the knapsack.
• n is the number of items.
• Each subsequent line contains two integers wi and vi, representing the weight and value of the \(i\)-th item.

outputFormat

The output is written to stdout and should be a single integer: the maximum total value that can be carried without exceeding the weight capacity \(W\).

## sample

50 3
10 60
20 100
30 120

220