logo AlgoBeat OnlineJudge
登录 注册

#102920. [BZOJ 2920] [Poi1998]How to pack containers

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

工厂的产品要装入圆柱形盒子。所有的盒子都是一样的底,盒子的高是一个 的乘方的非负整数。例如,对一些 其值等于 ,数字 (指数)称作盒子的尺寸。所有盒子包含一样的货物,但是它们价值可以不同,早期制作出的货物更便宜。管理者决定,最早的(最便宜的)货物应该首先卖出;在仓库里,货物要装入集装箱,集装箱也是圆柱形的;每个集装箱的直径比盒子的直径要大一点,这样,盒子很容易放进集装箱。集装箱的高度是一个非负的 的乘方。这个数称为集装箱的尺寸。为了安全的运输需要用盒子装满集装箱,即放进集装箱的盒子的高度总和必须等于这个集装箱的高度。一套集装箱送到仓库,检查仓库中的盒子是否能装满所有的集装箱,如果能,求装入集装箱中货物的最小价值。

例如,考虑有 个盒子的仓库,它们的大小及它们中货物的价值如下:

1 3
1 2
3 5
2 1
1 4

尺寸为 个集装箱能够放入价值为 的盒子,或者三个总价值为 的盒子,在仓库中,尺寸为 的集装箱不能装满盒子。

任务:

编写程序:

  1. 读入仓库中货物的描述(大小,价值)和集装箱的描述(提供几个多少尺寸的集装箱);
  2. 检查仓库中的货物能否装入集装箱,若能,求出装入集装箱中货物的最小价值;
  3. 将结果输出。

输入格式

  • 第一行有一个整数 ,表示仓库中盒子总数;
  • 下面 行每行有两个由空格分开的非负整数,它们描述每一个盒子,其中第一个数是盒子的尺寸,第二个数是盒子中货物的价值,尺寸不超过 ,价值不超过
  • 下一行有一个整数 ,表示运输到仓库的集装箱数(提供的集装箱个数),再下面的 行,每行有两个由空格分开的整数,第一个数是集装箱的尺寸,第二个数是该尺寸的集装箱的总数,集装箱的最大数目是 ,集装箱的尺寸不超过

输出格式

输出只有一行:

  1. NIE——表示仓库中的盒子不能装满意集装箱;
  2. 一个整数――与 中相反的情况,则输出装入集装箱中货物的最小价值。

样例

样例输入 #1

5 
1 31 2
3 5
2 1
1 4
2
1 1
2 1

样例输出 #1

3

数据范围与提示

对于 的数据,