Knapsack Queries

You are given a list of n items, each with a value and a weight. Then, you are given q queries. In each query, you are provided with a subset of items (via their 1-indexed positions) and a maximum allowable weight L. Your task is to determine the maximum total value that can be achieved by selecting a combination of these items without the total weight exceeding L.

This problem is a variant of the classic 0/1 knapsack problem. The dynamic programming recurrence used to solve this problem is given by:

\(dp[w] = \max(dp[w], dp[w - w_i] + v_i)\)

where \(w_i\) and \(v_i\) are the weight and value of the item respectively, and \(dp[w]\) represents the maximum obtainable value with a knapsack capacity of \(w\).

inputFormat

The input is given via standard input (stdin) and has the following format:

1. An integer n representing the number of items.
2. n lines follow, each containing two space-separated integers: the value and weight of an item.
3. An integer q representing the number of queries.
4. For each query:
   1. A line containing two integers: M (the number of items available for selection in this query) and L (the maximum weight allowed).
   2. A line with M space-separated integers representing the 1-indexed indices of the items available for that query.

outputFormat

The output should be printed to standard output (stdout). For each query, output a single line containing the maximum total value that can be obtained without exceeding the weight limit.

## sample

3
10 5
20 7
30 9
1
3 20
1 2 3

50

</p>