82700 - 机器人

NOI2025 正在绍兴举办，小 Y 为闭幕式表演制作了一个机器人并打算操控它从仓库走到礼堂。

绍兴的道路系统可以简化为 n 个路口以及连接这些路口的 m 条 单行道路，且每条道路有一定的长度。为了方便将道路系统录入机器人的芯片，小 Y 对每一个路口连接的所有道路进行了编号。具体而言，若有 d 条道路以路口 x 为起点，则这 d 条道路会被小 Y 按照某种顺序编号为 1 \sim d，分别称作以 x 为起点的第 1 \sim d 条道路。

小 Y 的机器人内部有一个参数 p。给定参数 p 的上限 k 与修改费用 v_1, v_2, \ldots, v_k-1, w_2, w_3, \ldots, w_k。小 Y 将按照如下规则设置与修改机器人的参数：

• 初始时，小 Y 将参数 p 设置为 1。
• 在 任意时刻，小 Y 可以远程控制机器人修改参数：
  • 若 p < k，则小 Y 可以花费 v_p 的费用将 p 增加 1，即 p \leftarrow p + 1；
  • 若 p > 1，则小 Y 可以花费 w_p 的费用将 p 减少 1，即 p \leftarrow p - 1。

初始时，小 Y 的机器人位于机器人仓库，即路口 1。当机器人位于路口 x 时，记以路口 x 为起点的第 p 条道路的终点为 y，道路长度为 z，则小 Y 可以花费 z 的费用操控机器人从 x 走到 y。特别地，若以路口 x 为起点的道路不足 p 条，则小 Y 无法操控机器人走动。

小 Y 并不知道闭幕式表演所在的礼堂位于哪个路口，因此他需要对每个路口都做好准备。请你帮助他求出将机器人从仓库移动到每个路口所需费用的最小值。

输入的第一行包含一个非负整数 c，表示测试点编号。c = 0 表示该测试点为样例。

输入的第二行包含三个正整数 n, m, k，分别表示路口数量、道路数量与参数 p 的上限。

输入的第三行包含 k - 1 个非负整数 $v1, \ldots, v{k-1}，表示增加参数 p$ 的费用。

输入的第四行包含 k - 1 个非负整数 w_2, \ldots, w_k，表示减少参数 p 的费用。

输入的第 i + 4（1 \leq i \leq n）行包含若干个正整数，其中第一个非负整数 d_i 表示以路口 i 为起点的道路数量，接下来 2d_i 个正整数 y_i,1, z_i,1, y_i,2, z_i,2, \ldots, y_i,d_i, z_i,d_i，表示以路口 i 为起点的道路，其中 y_i,j, z_i,j（1 \leq j \leq d_i）分别表示编号为 j 的道路的终点与长度。

输出一行 n 个整数，其中第 i（1 \leq i \leq n）个数表示小 Y 将机器人从仓库移动到路口 i 所需费用的最小值。特别地，若小 Y 无法将机器人从仓库移动到该路口，则输出 -1。

样例 1 解释

小 Y 可以按照以下方案将机器人分别从仓库移动到路口 1 \sim 4：

• 对于路口 1：小 Y 的机器人初始时即位于路口 1，因此所需费用为 0。
• 对于路口 2：小 Y 操控机器人沿以路口 1 为起点的第 1 条道路走到路口 2，所需费用为 5。
• 对于路口 3：小 Y 将参数 p 增加 1，然后操控机器人沿以路口 1 为起点的第 2 条道路走到路口 3，所需费用为 2 + 1 = 3。
• 对于路口 4：小 Y 将参数 p 增加 1，然后操控机器人沿以路口 1 为起点的第 2 条道路走到路口 3，再操控机器人沿以路口 3 为起点的第 2 条道路走到路口 4，所需费用为 2 + 1 + 1 = 4。

可以证明，上述移动方案的所需费用均为最小值。

• 对于路口 5：由于小 Y 无法将机器人移动到路口 5，因此输出 -1。

对于所有测试数据，保证：

• 1 \leq n, m \leq 3 \times 10^5，1 \leq k \leq 2.5 \times 10^5；
• 对于所有 1 \leq i \leq k - 1，均有 0 \leq v_i \leq 10^9；
• 对于所有 2 \leq i \leq k，均有 0 \leq w_i \leq 10^9；
• 对于所有 1 \leq i \leq n，均有 $0 \leq di \leq k，且 \sum{i=1}^{n} d_i = m$；
• 对于所有 1 \leq i \leq n，$1 \leq j \leq di，均有 1 \leq y{i,j} \leq n，1 \leq z_{i,j} \leq 10^9$。

NOI