Maximum Value Orders with Knapsack

You are given a warehouse with n items and m orders. Each item is characterized by its weight and value. For each order, you are only allowed to consider the first k items in the list. Then, using these k items, you need to select some items (each item can be chosen at most once) such that their total weight does not exceed the given weight capacity W of the cart, and the total value is maximized.

The problem can be formulated with the following constraints:

• Given two integers \( n \) (number of items) and \( m \) (number of orders).
• A list of items where each item \( i \) has a weight \( w_i \) and a value \( v_i \).
• A list of orders; each order is described by a pair of integers \( (k, W) \), where \( k \) means only the first \( k \) items from the list can be considered, and \( W \) is the weight capacity for that order.

Your task is to compute, for each order, the maximum total value of items that can be picked without exceeding the weight capacity \( W \). The classical 0-1 knapsack dynamic programming approach is applicable here.

Note: All formulas should be rendered using LaTeX. For instance, the weight capacity condition is \( \sum_{i \in S} w_i \leq W \) and the objective is to maximize \( \sum_{i \in S} v_i \).

inputFormat

The input is given via stdin in the following format:

 n m
 w1 v1
 w2 v2
 ...
 wn vn
 k1 W1
 k2 W2
 ...
 km Wm

where:

• The first line contains two integers \( n \) and \( m \).
• The next \( n \) lines each contain two integers representing the weight and value of an item.
• The following \( m \) lines each contain two integers representing an order: the first integer \( k \) tells you how many items (from the beginning of the list) you can consider, and the second integer \( W \) is the weight capacity for that order.

outputFormat

For each order, output the maximum total value achievable under the order's constraints. The answers for the orders should be printed to stdout, each on a separate line.

## sample

5 2
2 3
3 4
4 5
5 6
6 7
3 10
2 5

12
7

</p>