分数: 2100 点
问题陈述
有 N 珠宝店编号 1 to N.
商店 i (1 \leq i \leq N) 出售 K_i 种珠宝。 的 j- 这些珠宝中的第一个 (1 \leq j \leq K_i) 的尺寸和价格为 S_{i,j} 和 P_{i,j}分别和本店有 C_{i,j} 此类珠宝有库存。
据说有一个首饰盒 好 如果满足以下所有条件:
- 对于每个珠宝店,盒子中包含一件在那里购买的珠宝。
- 以下所有内容
满足 M 限制。
- 限制 i (1 \leq i \leq M): (在商店购买的珠宝的尺寸 V_i)\leq (在商店购买的珠宝的尺寸 U_i)+W_i
答案 Q 问题。 在 i第一个问题,给定一个整数 A_i,求出需要购买的珠宝的最低总价 A_i 好的首饰盒。如果无法制作 A_i 好的首饰盒,报告这个事实。
约束
- 1 \leq N \leq 30
- 1 \leq K_i \leq 30
- 1 \leq S_{i,j} \leq 10^9
- 1 \leq P_{i,j} \leq 30
- 1 \leq C_{i,j} \leq 10^{12}
- 0 \leq M \leq 50
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- 0 \leq W_i \leq 10^9
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 3 \times 10^{13}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Description of Shop 1 Description of Shop 2 \vdots Description of Shop N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M Q A_1 A_2 \vdots A_Q
店铺说明 i (1 \leq i \leq N) 的格式如下:
K_i
S_{i,1} P_{i,1} C_{i,1}
S_{i,2} P_{i,2} C_{i,2}
\vdots
S_{i,K_i} P_{i,K_i} C_{i,K_i}
输出
打印 Q 行。 的 i第行应包含需要购买的珠宝的最低总价 A_i 好的首饰盒,或者 -1 如果不可能制作它们。
示例输入 1
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
示例输出 1
3 42 -1
让 (i,j) 代表 j- 第 颗珠宝已在商店出售 i。 每个查询的答案如下:
- A_1=1: 制作一个盒子 (1,2),(2,2),(3,1) 成本 1+1+1=3,这是最佳的。
- A_2=2: 制作一个盒子 (1,1),(2,1),(3,1) 和另一个 (1,2),(2,3),(3,2) 成本 (10+10+1)+(1+10+10)=42,这是最佳的。
- A_3=3:我们无法制作三个好盒子。
示例输入 2
5 5 86849520 30 272477201869 968023357 28 539131386006 478355090 8 194500792721 298572419 6 894877901270 203794105 25 594579473837 5 730211794 22 225797976416 842538552 9 420531931830 871332982 26 81253086754 553846923 29 89734736118 731788040 13 241088716205 5 903534485 22 140045153776 187101906 8 145639722124 513502442 9 227445343895 499446330 6 719254728400 564106748 20 333423097859 5 332809289 8 640911722470 969492694 21 937931959818 207959501 11 217019915462 726936503 12 382527525674 887971218 17 552919286358 5 444983655 13 487875689585 855863581 6 625608576077 885012925 10 105520979776 980933856 1 711474069172 653022356 19 977887412815 10 1 2 231274893 2 3 829836076 3 4 745221482 4 5 935448462 5 1 819308546 3 5 815839350 5 3 513188748 3 1 968283437 2 3 202352515 4 3 292999238 10 510266667947 252899314976 510266667948 374155726828 628866122125 628866122123 1 628866122124 510266667949 30000000000000
示例输出 2
26533866733244 13150764378752 26533866733296 19456097795056 -1 33175436167096 52 33175436167152 26533866733352 -1