AT_agc043_f.[AGC043F] Jewelry Box

有 $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$ 个询问（$1 \leq i \leq Q$），给定整数 $A_i$，请你求出准备 $A_i$ 个好的珠宝盒时，所需购买珠宝的总价格的最小值。如果无法准备 $A_i$ 个好的珠宝盒，请输出相应的信息。

输入以如下格式从标准输入给出。

$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}$ $\cdots$ $S_{i,K_i}$ $P_{i,K_i}$ $C_{i,K_i}$

输出 $Q$ 行。第 $i$ 行输出准备 $A_i$ 个好的珠宝盒时所需购买珠宝的总价格的最小值。如果无法准备 $A_i$ 个好的珠宝盒，则输出 $-1$。

限制

• $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}$
• 输入均为整数。

样例解释 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$：无法准备 $3$ 个好的珠宝盒。

由 ChatGPT 4.1 翻译