Polish version    English version  
  History of OI -> V OI 1997/1998 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
V Olimpiada Informatyczna 1997/1998

Task: PAK
Author: Wojciech Rytter
How to pack cointainers?

II stage contest  

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 2, i.e. it is equal to 2i for some i=0,1,2,... . The number i (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.

Example

Consider a warehouse with 5 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 1 and 2 can be tightly packed with two boxes of total value 3, 4 or 5, or three boxes with total value 9. The container of size 5 cannot be tightly packed with boxes from the warehouse.

Task

Write a program that:

  • reads descriptions of boxes (size, value) from a warehouse and descriptions of containers (how many containers of a given size we have) from the text file PAK.IN;
  • checks if all containers can be tightly packed with boxes from the warehouse and if so, computes the minimal value of goods that can be tightly packed into these containers;
  • writes the result to the text file PAK.OUT.

Input

In the first line of the input file PAK.IN there is an integer n, 1<=n<=10000, which is the number of boxes in the warehouse. In each of the following n 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 1000 and the value is not greater than 10000. The next line contains a positive integer q, which is the number of different sizes of containers delivered to the warehouse. In each of the following q 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 5000, a size of a container is not greater than 1000.

Output

Your program should write to the first and only line of the file PAK.OUT

  • a single word NIE (which means NO in Polish) if it is not possible to pack the containers from the given set tight with the boxes from the warehouse, or
  • a single integer equal to the minimal value of goods in boxes with which all the containers from the given set can be packed tight.

Example

For the input file PAK.IN:

5
1 3
1 2
3 5
2 1
1 4
2
1 1
2 1
the correct result is the output file PAK.OUT:
3




Print friendly version