SP15312 VPL2_BE - Annoying Coins Quest

小Tita一直被硬币烦扰不已，于是她制定了一个公式，为每笔交易赋予一个厌烦程度。这个公式相当简单：每个硬币 $c$ 有一个转移厌烦值 $T_c$ 和保留厌烦值 $K_c$。因此，每笔交易的总厌烦程度 $A$ 可以定义为转移厌烦值 $A_T$ 与保留厌烦值 $A_K$ 的总和。具体为： - $A = A_T + A_K$ - $A_T = \sum (T_c \times \text{转移的硬币数量})$ - $A_K = \sum (K_c \times \text{保留的硬币数量})$ 我们知道，卖家有无限数量的每种硬币，他们根本不在乎Tita自创的厌烦度公式。你的任务是：给定现有硬币种类、交易所需金额和Tita手中的硬币数，求出Tita所能保证的最小总厌烦程度。如果交易无法做到，则输出 -1。

第一行是整数 $T$，表示共有多少组测试用例。接下来每一组测试用例描述如下： 第一行有两个整数 $N$ 和 $C$，分别表示硬币的种类数和交易的金额。随后 $N$ 行，每行都用三个整数 $V_i$、$T_i$ 和 $K_i$ 描述一种硬币，分别是硬币的面值、转移厌烦值以及保留厌烦值。最后一行有 $N$ 个整数 $A_i$，表示Tita手中拥有的每种硬币的数量，顺序与前面描述一致。

对于每个测试用例，输出一行格式如 `Scenario #i: x`，其中 $i$ 是测试用例编号（从 1 开始），$x$ 是Tita能保证的最小总厌烦程度；如果交易无法进行，则输出 -1。 ## 数据范围 - $1 \le T \le 10$ - $1 \le N \le 100$ - $1 \le C \le 10^5$ - $1 \le V_i, T_i, K_i \le 10^5$ - $0 \le A_i \le 10^5$ **本翻译由 AI 自动生成**