珠宝商店
时间限制:4.0s 内存限制:512.0MB
问题描述
有 N个商店,其中第i个商店卖Ki种珠宝,第j(1≤j≤Ki) 种珠宝拥有三个独立的属性 (S,P,C),依次表示重量,价格,数量。 现在有 Q 次相互独立的询问,每次给定一个 Ai,询问能否构造出 Ai个“珠宝盒”,如果可以则输出最小花费 (即购买的珠宝价值之和),否则输出−1。
一个“珠宝盒”是一个包含N 个珠宝的盒子,且满足如下条件:
• 盒子内部的第 i个珠宝从第i个珠宝商店处购买。 • 满足 M 条约束:其中第 i条约束表示盒子内的第 Vi个珠宝的重量不应超过第 Ui个珠宝的重量 +Wi。
输入格式
第一行一个整数 N。接下来 N 段,第 i 段描述第i个商店。 对于第i段: 第一行一个整数 Ki。 接下来Ki行,第j 行三个整数 Si,j,Pi,j,Ci,j,意义如上。 然后一个整数 M。 接下来 M 行,每行三个整数 Ui,Vi,Wi,意义如上。 然后一个整数 Q。 接下来 Q 行,每行一个整数 Ai。
输出格式
Q行,表示每个询问的答案。
样例输入
3
2
1 10 1
3 1 1
3
1 10 1
2 1 1
3 10 1
2
1 1 1
3 10 1
2
1 2 0
2 3 0
3
1
2
3
样例输出
3
42
-1
评测用例规模与约定
对于 70% 的数据,Q≤3000。 对于 100% 的数据:
• 1≤N,Ki≤30
• 1≤Si,j≤109
• 1≤Pi,j≤30
• 1≤Ci,j≤1012
• 0≤M≤50
• 1≤Ui,Vi≤N
• Ui=Vi
• 0≤Wi≤109
• 1≤Q≤105
• 1≤Ai≤3×1013