Batch Operation Knapsack Problem

You are given a series of batches. Each batch consists of a list of operations where every operation is represented as a pair of integers (T, V) meaning that the operation takes T units of time and yields a value of V. In addition, a maximum time limit T_max is provided for each batch.

Your task is to select a subset of operations from each batch such that the total time does not exceed T_max and the sum of the values is maximized. Formally, this is a variant of the 0/1 Knapsack problem where the weights are the time requirements and the values are the operation values.

The problem can be modeled by the following equation in LaTeX format:

\[ \text{max} \; \sum_{i=1}^{n} V_i \quad \text{subject to} \quad \sum_{i=1}^{n} T_i \leq T_{max}, \quad T_i \in \{0, T_i\} \]

For each batch, output the result in the following format:

For Batch #i:
X

where i is the batch number (starting from 1) and X is the maximum sum of values achievable without exceeding the time limit.

inputFormat

The first line of input contains an integer representing the number of batches, b.

For each batch:

• The first line contains an integer M representing the number of operations.
• The next M lines each contain two space-separated integers T and V indicating the time and value of an operation.
• The following line contains an integer T_max, the maximum time allowed for the batch.

All input is provided via stdin.

outputFormat

For each batch, output a line in the form:

For Batch #i:
X

where i is the batch number starting at 1 and X is the maximal sum of operation values that can be performed without exceeding the time limit. All output should be written to stdout.

## sample

1
3
3 10
2 15
1 30
4

For Batch #1:
45

</p>