CF1131G Most Dangerous Shark

Semyon 参加了世界海洋中最负盛名的比赛，争夺“最危险鲨鱼”的称号。在这场比赛中，鲨鱼们要在多个项目中竞争：快速游泳、伪装、地图导航等。现在，Semyon 正在参加“破坏”项目。 在这个项目中，鲨鱼面前有 $m$ 个多米诺骨牌。所有骨牌排成一行，但每个骨牌的高度可能不同。相邻骨牌之间的距离为 $1$。此外，每个骨牌都有一个整数表示的代价。目标是让所有骨牌倒下。为此，鲨鱼可以选择推动任意一个骨牌向左或向右倒下，它会朝该方向开始倒下。如果在倒下过程中骨牌碰到其他骨牌，这些骨牌也会朝同一方向倒下，从而引发连锁反应，使许多骨牌倒下。一个倒下的骨牌会碰到另一个骨牌，当且仅当它们之间的距离严格小于倒下骨牌的高度，骨牌不一定要相邻。 当然，任何鲨鱼都能轻松让所有骨牌倒下，所以目标不是让所有骨牌倒下，而是以最小的代价完成。破坏的总代价是鲨鱼需要推动的骨牌的代价之和。 Semyon 已经赢得了前面的项目，但在这个项目上不够聪明，无法获胜。请帮助 Semyon，计算他让所有骨牌倒下所需的最小总代价。

为了减少输入规模，多米诺骨牌的高度和代价以“块”为单位描述。 第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 250\,000, 1 \leq m \leq 10^7$），分别表示块的数量和 Semyon 需要推倒的多米诺骨牌总数。 接下来是 $n$ 个块的描述。每个块的描述包含三行。 第一行包含一个整数 $k_i$（$1 \leq k_i \leq 250\,000, \sum_{i = 1}^{n}{k_i} \leq 250\,000$），表示该块中多米诺骨牌的数量。 第二行包含 $k_i$ 个整数 $a_j$（$1 \leq a_j \leq m$），表示该块中每个骨牌的高度。 第三行包含 $k_i$ 个整数 $c_j$（$1 \leq c_j \leq 100\,000$），表示该块中每个骨牌的代价。 然后描述多米诺骨牌的排列顺序（从左到右）。 排列描述的第一行包含一个整数 $q$（$n \leq q \leq 250\,000$），表示多米诺骨牌排列中块的数量。 接下来的 $q$ 行，每行包含两个整数 $id_i, mul_i$（$1 \leq id_i \leq n$，$1 \leq mul_i \leq 100\,000$），表示接下来的 $k_{id_i}$ 个骨牌来自第 $id_i$ 个块，并且它们的代价都乘以 $mul_i$。 保证 $\sum_{i = 1}^{q}{k_{id_i}} = m$，且每个块在排列中至少使用一次。

输出一个整数，表示让所有多米诺骨牌倒下所需的最小总代价。

在第一个样例中，Semyon 面前有 $7$ 个多米诺骨牌。它们的高度为 $[3, 1, 2, 2, 1, 2, 2]$，代价为 $[4, 3, 6, 3, 1, 2, 1]$。Semyon 应该推动第 $7$ 个骨牌向左倒下，它会带倒第 $6$ 个骨牌。第 $6$ 个骨牌倒下时会带倒第 $5$ 个骨牌，但第 $5$ 个骨牌不会再带倒其他骨牌。然后 Semyon 应该推动第 $1$ 个骨牌向右倒下，它会带倒第 $2$ 和第 $3$ 个骨牌。第 $3$ 个骨牌倒下时会带倒第 $4$ 个骨牌。这样所有骨牌都被推倒。 在第二个样例中，只有一个骨牌，代价为 $10000000000$。 由 ChatGPT 4.1 翻译