In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Products of a factory are packed into cylindrical boxes. All boxes have the same bases. A height of a box is a non-negative integer being a power of , i.e. it is equal to for some . The number (exponent) is called a size of a box. All boxes contain the same goods but their value may be different. Goods produced earlier are cheaper. The management decided, that the oldest (cheapest) goods should be sold out first. From the warehouse goods are transported in containers. Containers are also cylindrical. A diameter of each container is a little bigger than a diameter of a box, so that boxes can be easily put into containers. A height of a container is a non-negative power of 2. This number is called a size of a container. For safe transport containers should be tightly packed with boxes, i.e. the sum of heights of boxes placed in a container have to be equal to the height of this container.
A set of containers was delivered to the warehouse. Check if it is possible to pack all the containers tight with boxes that are currently stored in the warehouse. If so, find the minimal value of goods that can be tightly packed into these containers.
Consider a warehouse with boxes. Their sizes and values of their contents are given below:
1 3 1 2 3 5 2 1 1 4
Two containers of size and can be tightly packed with two boxes of total value , or , or three boxes with total value . The container of size cannot be tightly packed with boxes from the warehouse.
Write a program that:
In the first line of the standard input there is an integer , , which is the number of boxes in the warehouse. In each of the following lines there are written two non-negative integers separated by a single space. These numbers describe a single box. First of them is the size of the box and the second — the value of goods contained in this box. The size is not greater than and the value is not greater than .
The next line contains a positive integer , which is the number of different sizes of containers delivered to the warehouse. In each of the following lines there are two positive integers separated by a single space. The first integer is the size of a container and the second one is the number of containers of this size. The maximal number of containers is , a size of a container is not greater than .
Your program should write to the first and only line of the standard output:
For the input data:
5 1 3 1 2 3 5 2 1 1 4 2 1 1 2 1
the correct result is:
Task author: Wojciech Rytter.