How to Pack Containers?

A factory packs its products into cylindrical boxes. All boxes share the same base. The height of a box is always a power of two: it equals $2^i$ for some integer $i = 0, 1, 2, \ldots$. This exponent $i$ is called the size of the box. Every box holds the same kind of goods, but the value of its contents may differ. Goods produced earlier are cheaper, and the warehouse wants to ship the oldest (cheapest) goods first.

Goods leave the warehouse inside containers. A container is also cylindrical, and its diameter is a little larger than a box so that boxes slide in easily. The height of a container is a power of two as well, and that exponent is called the size of the container. For safe transport a container must be packed tight with boxes: the heights of the boxes placed inside one container must add up to exactly the height of that container. Each box may go into at most one container, and you need not use every box in the warehouse.

A set of containers has arrived at the warehouse. Decide whether all of the given containers can be packed tight using the boxes in the warehouse. If they can, find the minimum possible total value of the goods placed into the containers.

Write a program that:

• reads, from standard input, the boxes in the warehouse (each as a size and a value) and the containers that arrived (as a count for each size);
• checks whether all containers can be packed tight with the warehouse boxes and, if so, computes the minimum total value of the goods that are packed;
• writes the result to standard output.

The first line contains an integer $n$, the number of boxes in the warehouse ($1 \le n \le 10000$). Each of the next $n$ lines contains two non-negative integers separated by a single space describing one box: the first is the size of the box and the second is the value of the goods it holds. A size is at most 1,000 and a value is at most 10,000.

The next line contains a positive integer $q$, the number of distinct container sizes that arrived at the warehouse. Each of the next $q$ lines contains two positive integers separated by a single space: the first is a container size and the second is the number of containers of that size. There are at most 5,000 containers in total, and a container size is at most 1,000.

On the first and only line of standard output, print:

• the single word NIE if it is impossible to pack the given set of containers tight with the boxes from the warehouse, or
• a single integer equal to the minimum total value of the goods in the boxes with which all of the containers can be packed tight.