Order Discount Optimization

You are given a list of orders and a list of available discounts. Each order is represented by two integers: the price per item (in cents) and the quantity ordered. There are three types of discounts available:

1. Percentage Discount: Given in the format percentage X, this discount deducts (\lfloor \text{total cost} \times X/100 \rfloor) cents from the order’s total cost.

2. Flat Discount: Given in the format flat Y, this discount deducts a fixed amount of Y cents from the order’s total cost.

3. BOGO Discount: Denoted by the string bogo, this discount makes every second item free. The effective cost is (\text{price} \times (\text{quantity} - \lfloor \text{quantity}/2 \rfloor)).

For each order, you need to determine the minimal possible cost by applying at most one of the available discounts (or none if that yields the best result). Note that if multiple discount types are offered, you should choose the one that minimizes the cost.

Input/Output Note: All inputs are read from standard input (stdin) and outputs should be written to standard output (stdout).

inputFormat

The first line contains an integer (N) representing the number of orders. The next (N) lines each contain two space-separated integers: the price (in cents) and the quantity for an order. The following line contains an integer (M) representing the number of discounts available. The next (M) lines each contain a discount in one of three formats:

• percentage X
• flat Y
• bogo

outputFormat

Output (N) lines, each containing the minimal cost (in cents) for the corresponding order after applying the best discount.## sample

3
1000 2
500 3
1200 1
2
percentage 10
flat 150

1800
1350
1050