Maximize Gem Value

You are given n gems, each with a specific weight and value. You also have a bag that can carry a maximum weight of capacity. Your task is to choose a subset of gems to maximize the total value, without exceeding the bag’s capacity.

This is a classic 0/1 knapsack problem. Formally, given:

• \(n\): number of gems.
• \(\text{capacity}\): maximum weight capacity of the bag.
• A list of gems where each gem \(i\) has a weight \(w_i\) and a value \(v_i\).

You need to compute the maximum total value that can be obtained, such that the total weight does not exceed \(\text{capacity}\).

The solution typically uses dynamic programming, where we define a DP array such that \(dp[j]\) represents the maximum value achievable with a capacity \(j\).

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains two integers \(n\) and \(\text{capacity}\), separated by a space.
• The next \(n\) lines each contain two integers \(w\) and \(v\) representing the weight and value of a gem, respectively.

outputFormat

Output to stdout a single integer: the maximum total value that can be carried in the bag.

4 7
2 10
3 20
4 30
5 40

50