题目描述

注意：本题时间限制为 $2.5\text{s}$。

农夫约翰有 $N$ 堆干草捆（$1 \le N \le 5 \cdot 10^5$），其中第 $i$ 堆包含 $a_i$ 个干草捆（$1 \le a_i \le 10^9$）。他想移走所有这些干草捆，并且有 $M$（$1 \le M \le 2500$）头奶牛可供雇佣。如果雇佣第 $i$ 头奶牛，它会以花费 $c_i$（$1 \le c_i \le 10^9$）的代价，重复执行以下操作 $s_i$ 次（$1 \le s_i \le 100$）：

• 如果当前堆中至少有 $p_i$ 个干草捆（$1 \le p_i \le 10^9$），那么这头奶牛会移走一个干草捆。
• 如果当前堆中的干草捆少于 $p_i$ 个，则奶牛什么也不做。

对于每一堆干草，FJ 希望将其中的所有干草捆全部移走。他通过按顺序雇佣奶牛（同一头奶牛可多次雇佣）直到该堆变空来实现。请帮助 FJ 确定移空每一堆干草所需的最小总花费。

输入格式

第一行包含 $T$（$1 \le T \le 100$），表示独立测试用例的数量。每个测试用例的格式如下：

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$。

第三行包含一个整数 $M$。

接下来 $M$ 行，每行包含三个整数 $p_i, s_i, c_i$。

保证奶牛能够移空每一堆中的所有干草捆。此外，保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$，所有测试用例的 $M$ 之和不超过 $2500$。

输出格式

对于每个测试用例，输出一行 $N$ 个空格分隔的整数，其中第 $i$ 个整数表示移空第 $i$ 堆干草所需的最小花费。

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

29 155 21
73 328 50

提示

第一个测试用例：对于初始大小为 $10$ 的最后一堆，我们可以雇佣一次奶牛 $3$，花费 $5$，它会移走两次干草捆（不是三次，因为第二次移走后剩余干草捆数量变为 $8$）。然后我们可以雇佣两次奶牛 $2$，移走剩余的 $8$ 个干草捆，使堆变空。总花费为 $5 + 8 + 8 = 21$。

第二个测试用例：满足 $\max(s) = 1$。

计分规则

• 输入 $2$-$3$：$a_i \le 100$
• 输入 $4$-$5$：$\max(s) = 1$
• 输入 $6$-$9$：$\max(s) \le 4$
• 输入 $10$-$15$：$\max(s) \le 20$
• 输入 $16$-$21$：无额外限制。

翻译由 DeepSeek V4 Pro 完成