问题描述

有 $N$ 家珠宝店，编号从 $1$ 到 $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$

店铺 1 的描述

店铺 2 的描述

$\vdots$

店铺 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)$ 表示在第 $i$ 家店出售的第 $j$ 种珠宝。每个查询的答案如下：

• $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