有 $N$ 个珠宝商店。

每个商店卖 $K_i$ 种珠宝，第 $i$ 个商店的第 $j(1\le j\le K_i)$ 种珠宝拥有三个独立的属性 $(S,P,C)$ 依次表示重量，价格，数量。

现在有 $Q$ 组询问，每次给定一个 $A_i$，询问能否够构造 $A_i$ 个“珠宝盒”，如果可以则输出最小的花费（即购买的珠宝的价格之和）否则输出 $-1$

一个“珠宝盒”是一个包含 $N$ 个珠宝的盒子，且满足如下条件：

• 盒子内部的第 $i$ 个珠宝从第 $i$ 个珠宝商店处购买。
• 满足 $M$ 条约束：
  • 对于第 $i$ 条约束：此盒子内第 $V_i$ 珠宝的重量应当不超过第 $U_i$ 个珠宝的重量 $+ W_i$

$N,K_i\le 30,S_{i,j}\le 10^9,P_{i,j}\le 30,C_{i,j}\le 10^{12},M\le 50$

$Q\le 10^5,A_i\le 3\times 10^{13},W_i\le 10^9$

translated by Soulist