A6755 | 「NOI2025」机器人

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

从文件 robot.in 中读入数据。

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

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

输入的第三行包含 $k - 1$ 个非负整数 $v_1, \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$ 的道路的终点与长度。

输出到文件 robot.out 中。

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