#P18802. [POI1998] 装箱

[POI1998] 装箱

[POI1998] 装箱

题目描述

仓库里有 nn 个圆柱形盒子,它们的底面完全相同。一个盒子的大小用整数 ss 表示,它的高度为 2s2^s。每个盒子还有一个非负整数价值。

现在有若干圆柱形集装箱,它们也具有相同的底面;大小为 tt 的集装箱高度为 2t2^t。每个集装箱必须恰好装满:放入其中的盒子高度之和必须等于该集装箱的高度。

每个盒子至多使用一次,不能拆开;可以剩下一些盒子不使用。不同集装箱之间不能共享盒子。

判断能否装满所有集装箱。如果可以,求所用盒子的价值总和的最小值。

输入格式

第一行一个整数 nn,1≤n≤100001\le n\le10000。

接下来 nn 行,每行两个整数 s,cs,c,表示一个盒子的大小和价值,0≤s≤10000\le s\le1000,0≤c≤100000\le c\le10000。

接下来一行一个正整数 qq,表示集装箱共有多少种不同的大小。

接下来 qq 行,每行两个正整数 t,kt,k,表示有 kk 个大小为 tt 的集装箱,1≤t≤10001\le t\le1000。各行的 tt 互不相同,所有集装箱数量之和不超过 50005000。

输出格式

若不能装满所有集装箱,输出 NIE。

否则输出最小价值总和。合法的最小值可以是 00。

样例输入

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

样例输出

3