#P18802. [POI1998] 装箱
[POI1998] 装箱
[POI1998] 装箱
题目描述
仓库里有 个圆柱形盒子,它们的底面完全相同。一个盒子的大小用整数 表示,它的高度为 。每个盒子还有一个非负整数价值。
现在有若干圆柱形集装箱,它们也具有相同的底面;大小为 的集装箱高度为 。每个集装箱必须恰好装满:放入其中的盒子高度之和必须等于该集装箱的高度。
每个盒子至多使用一次,不能拆开;可以剩下一些盒子不使用。不同集装箱之间不能共享盒子。
判断能否装满所有集装箱。如果可以,求所用盒子的价值总和的最小值。
输入格式
第一行一个整数 ,。
接下来 行,每行两个整数 ,表示一个盒子的大小和价值,,。
接下来一行一个正整数 ,表示集装箱共有多少种不同的大小。
接下来 行,每行两个正整数 ,表示有 个大小为 的集装箱,。各行的 互不相同,所有集装箱数量之和不超过 。
输出格式
若不能装满所有集装箱,输出 NIE。
否则输出最小价值总和。合法的最小值可以是 。
样例输入
5
1 3
1 2
3 5
2 1
1 4
2
1 1
2 1
样例输出
3