Person in Charge

Problem Description

NOI2025 is being held in Shaoxing, and Little Y has built a robot for the closing ceremony performance and plans to control it to move from the warehouse to the auditorium.

The road system in Shaoxing can be simplified as $n$ intersections and $m$ one-way roads connecting these intersections, each with a certain length. To facilitate the input of the road system into the robot's chip, Little Y has numbered all the roads originating from each intersection. Specifically, if there are $d$ roads starting from intersection $x$, these $d$ roads will be numbered by Little Y in some order as $1 \sim d$, referred to as the $1^{st}$ to $d^{th}$ roads starting from $x$.

Little Y's robot has an internal parameter $p$. Given the upper limit $k$ of the parameter $p$ and the modification costs $v_1, v_2, \ldots, v_{k-1}, w_2, w_3, \ldots, w_k$, Little Y will set and modify the robot's parameter according to the following rules:

• Initially, Little Y sets the parameter $p$ to $1$.
• At any time, Little Y can remotely control the robot to modify the parameter:
  • If $p < k$, Little Y can spend $v_p$ to increase $p$ by $1$, i.e., $p \leftarrow p + 1$;
  • If $p > 1$, Little Y can spend $w_p$ to decrease $p$ by $1$, i.e., $p \leftarrow p - 1$.

Initially, Little Y's robot is located at the robot warehouse, which is intersection $1$. When the robot is at intersection $x$, let the $p^{th}$ road starting from intersection $x$ have destination $y$ and length $z$. Then, Little Y can spend $z$ to control the robot to move from $x$ to $y$. Specifically, if there are fewer than $p$ roads starting from intersection $x$, Little Y cannot control the robot to move.

Little Y does not know which intersection the auditorium for the closing ceremony is located at, so he needs to prepare for every intersection. Please help him determine the minimum cost required to move the robot from the warehouse to each intersection.

Input Format

The first line of input contains a non-negative integer $c$, representing the test case number. $c = 0$ indicates that the test case is a sample.

The second line of input contains three positive integers $n, m, k$, representing the number of intersections, the number of roads, and the upper limit of the parameter $p$.

The third line of input contains $k - 1$ non-negative integers $v_1, \ldots, v_{k-1}$, representing the costs to increase the parameter $p$.

The fourth line of input contains $k - 1$ non-negative integers $w_2, \ldots, w_k$, representing the costs to decrease the parameter $p$.

The $(i + 4)^{th}$ line of input (for $1 \le i \le n$) contains several positive integers. The first non-negative integer $d_i$ represents the number of roads starting from intersection $i$, followed by $2d_i$ positive integers $y_{i,1}, z_{i,1}, y_{i,2}, z_{i,2}, \ldots, y_{i,d_i}, z_{i,d_i}$, representing the roads starting from intersection $i$, where $y_{i,j}, z_{i,j}$ (for $1 \le j \le d_i$) represent the destination and length of the $j^{th}$ road, respectively.

Output Format

Output one line containing $n$ integers, where the $i^{th}$ integer (for $1 \le i \le n$) represents the minimum cost required for Little Y to move the robot from the warehouse to intersection $i$. Specifically, if the robot cannot be moved to the intersection, output $-1$.

Samples

0
5 6 3
2 4
1 1
3 2 5 3 1 4 2
1 3 2
2 1 2 4 1
0
0

0 5 3 4 -1

Sample 1 Explanation

Little Y can use the following plans to move the robot from the warehouse to intersections $1 \sim 4$:

• For intersection $1$: The robot is initially at intersection $1$, so the cost is $0$.
• For intersection $2$: Little Y controls the robot to move along the $1^{st}$ road starting from intersection $1$ to intersection $2$, with a cost of $5$.
• For intersection $3$: Little Y increases the parameter $p$ by $1$, then controls the robot to move along the $2^{nd}$ road starting from intersection $1$ to intersection $3$, with a cost of $2 + 1 = 3$.
• For intersection $4$: Little Y increases the parameter $p$ by $1$, then controls the robot to move along the $2^{nd}$ road starting from intersection $1$ to intersection $3$, and then moves along the $2^{nd}$ road starting from intersection $3$ to intersection $4$, with a cost of $2 + 1 + 1 = 4$.

It can be proven that the costs of the above plans are all minimal.

• For intersection $5$: Since Little Y cannot move the robot to intersection $5$, the output is $-1$.

Sample 2

See the files robot/robot2.in and robot/robot2.ans in the contestant directory.

This sample satisfies the constraints of test cases $3 \sim 5$.

Sample 3

See the files robot/robot3.in and robot/robot3.ans in the contestant directory.

This sample satisfies the constraints of test cases $6 \sim 8$.

Sample 4

See the files robot/robot4.in and robot/robot4.ans in the contestant directory.

This sample satisfies the constraints of test cases $9, 10$.

Sample 5

See the files robot/robot5.in and robot/robot5.ans in the contestant directory.

This sample satisfies the constraints of test cases $16 \sim 18$.

Data Range

For all test data, the following guarantees hold:

• $1 \le n, m \le 3 \times 10^5$, $1 \le k \le 2.5 \times 10^5$;
• For all $1 \le i \le k - 1$, $0 \le v_i \le 10^9$;
• For all $2 \le i \le k$, $0 \le w_i \le 10^9$;
• For all $1 \le i \le n$, $0 \le d_i \le k$, and $\sum_{i=1}^{n} d_i = m$;
• For all $1 \le i \le n$, $1 \le j \le d_i$, $1 \le y_{i,j} \le n$, $1 \le z_{i,j} \le 10^9$.

• Special Property A: $v_1 = v_2 = \cdots = v_{k-1} = 0$ and $w_2 = w_3 = \cdots = w_k = 0$.
• Special Property B: For all $1 \le i \le n$, $1 \le j \le d_i$, $z_{i,j} = 1$.
• Special Property C: At most $10$ intersections $i$ satisfy $d_i \ge 10$.