Problem Description

An explorer needs to pass through a maze full of spacetime rifts. There are $n$ spacetime rifts (called nodes), numbered $1 \sim n$. The explorer may stay at any node for any length of time.

There are $m$ paths between the rifts. Each path is described by $(u_i, v_i, w_i, s_i, e_i)$, meaning there is an undirected path between node $u_i$ and node $v_i$. Traversing this path takes time $w_i$, and the explorer can enter and traverse it only when the current time is within the interval $[s_i, e_i]$ (therefore, after traversing this path, the arrival time at $v_i$ must be within $[s_i + w_i, e_i + w_i]$).

At the same time, the explorer has a chance to adjust the flow of time: when traversing some path, they may ignore the time restriction $[s_i, e_i]$. This skill can be used at most $k$ times.

Initially, the explorer is at node $1$ at time $0$. What is the minimum time needed to reach node $n$ from node $1$?

Input Format

The first line contains three integers $n, m, k$, separated by one space.

The next $m$ lines each contain five integers $u_i, v_i, w_i, s_i, e_i$, separated by one space, describing the $i$-th path. The graph may contain multiple edges and self-loops.

Output Format

Output one line containing one integer, the answer. If there is no possible path, output $-1$.

3 3 0
1 2 1 0 3
2 3 3 5 10
1 3 6 0 7

6

3 3 1
1 2 1 0 3
2 3 3 5 10
1 3 6 0 7

4

Hint

Sample Explanation

For Sample 1: You can directly take the path $1 \to 3$, which takes 6 units of time. Taking $1 \to 2 \to 3$ takes 8 units of time, because after reaching node 2 you need to wait until time 5 to continue.

For Sample 2: Since you have one chance to use the skill, first take $1 \to 2$, then use the skill once on $2 \to 3$, for a total time of 4.

Constraints and Conventions

For $10\%$ of the testdata, $2 \le n \le 5$.

For $20\%$ of the testdata, $2 \le n \le 10$.

For $40\%$ of the testdata, $2 \le n \le 100$.

For $60\%$ of the testdata, $2 \le n \le 1000$.

For $80\%$ of the testdata, $2 \le n \le 10000$.

For all testdata, $2 \le n \le 50000$, $1 \le m \le \min\left(\dfrac{n(n-1)}{2}, 10^5\right)$, $0 \le k \le 10$, $1 \le u_i, v_i \le n$, $0 \le s_i, e_i \le 4 \times 10^3$.

Translated by ChatGPT 5