0/1 Knapsack Problem

We are given a container with a weight capacity (W) and a collection of (N) items. Each item is described by its weight and its value. The task is to select a subset of these items such that the total weight does not exceed (W) and the total value is maximized. Each item can only be chosen once.

Input Format: The first line contains two integers (W) and (N). Each of the following (N) lines contains two integers representing the weight and value of an item.

Output Format: Output a single integer representing the maximum total value achievable.

inputFormat

The input begins with two space-separated integers (W) (the weight capacity) and (N) (the number of items). This is followed by (N) lines, each containing two space-separated integers representing the weight and the value of an item.

outputFormat

Output a single integer — the maximum total value that can be obtained without exceeding the weight capacity (W).## sample

50 3
10 60
20 100
30 120

220