题目描述

某城市有 $n$ 个站点，编号分别为 $1,2,\dots,n$，站点之间由 $m$ 条双向渠道相连。

第 $i$ 条渠道连接站点 $u_i$ 与 $v_i$，完整通过它需要 $t_i$ 个单位时间。受日常维护工作的影响，第 $i$ 条渠道只在时间区间 $[l_i,r_i]$ 内开放：你必须在一个时刻 $x$ 进入渠道，满足 $l_i\le x$ 且 $x+t_i\le r_i$，才能顺利通过；否则这条渠道不能使用。

你从 $1$ 号站点、时刻 $0$ 出发，可以在任意站点停留任意长的时间。等待本身不消耗额外的时间，你只需要把等待的时间计入到达时刻。

由于体力有限，你恰好要乘坐 $K$ 条渠道：每完整通过一条渠道算乘坐一次。你可以重复经过同一条渠道，只要每次通过时它都处于开放状态，并且每次都要计入乘坐次数。

请你求出恰好乘坐 $K$ 条渠道后，最早能在什么时刻到达 $n$ 号站点；如果恰好乘坐 $K$ 条渠道无法到达 $n$ 号站点，输出 $-1$。

渠道的连接关系不保证是一棵树：两个站点之间可能有多条渠道，整张图也可能存在环。渠道的开放区间不会随时间循环，每条渠道只在给定的那一段时间内开放一次，错过之后就只能绕行。

每条渠道的开放区间都满足 $l_i+t_i\le r_i$，因此总存在至少一个可以进入的时刻；

渠道在两个方向上都可以通行，且两个方向的通行时间相同。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n,m,K$。

接下来 $m$ 行，第 $i$ 行包含五个整数 $u_i,v_i,t_i,l_i,r_i$，依次表示第 $i$ 条渠道连接的两个站点、通过耗时、开放区间的左端点和右端点。

输入保证 $l_i+t_i\le r_i$，即每条渠道至少存在一个可以完整通过的时刻。

如果恰好坐满 $K$ 条渠道仍然到不了 $n$ 号站点，输出 $-1$。

输出格式

输出到标准输出中。

输出一行一个整数，表示恰好坐满 $K$ 条渠道后最早的到达时刻；若无法到达，输出 $-1$。

样例 1 输入

3 3 2
1 2 2 0 10
2 3 2 0 10
1 3 10 0 5

样例 1 输出

4

样例 1 解释

走 $1\to 2\to 3$ 需要恰好乘坐 $2$ 条渠道：时刻 $0$ 进入第一条渠道，时刻 $2$ 到达 $2$ 号站点；随即进入第二条渠道，时刻 $4$ 到达 $3$ 号站点。

直达渠道只需要乘坐 $1$ 条，不符合"恰好 $K=2$ 条"的要求；而且它在时刻 $5$ 就已经关闭，本来也无法完整通过。

样例 2 输入

4 4 1
1 2 1 0 100
2 3 1 0 100
3 4 1 0 100
1 4 10 0 100

样例 2 输出

10

样例 2 解释

只允许乘坐 $1$ 条渠道，因此只能选择直达渠道，耗时 $10$。

样例 3

见选手目录下的 channel/channel3.in 与 channel/channel3.ans。

该样例满足测试点 $3\sim 5$ 的约束条件。

样例 4

见选手目录下的 channel/channel4.in 与 channel/channel4.ans。

该样例满足测试点 $6\sim 8$ 的约束条件。

样例 5

见选手目录下的 channel/channel5.in 与 channel/channel5.ans。

该样例满足测试点 $22\sim 25$ 的约束条件。

数据范围

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

• $2\le n\le 2\times 10^{5}$，$1\le m\le 2\times 10^{5}$，$1\le K\le 20$；
• 对于所有 $1\le i\le m$，均有 $1\le u_i\ne v_i\le n$；
• 对于所有 $1\le i\le m$，均有 $1\le t_i\le 10^{9}$；
• 对于所有 $1\le i\le m$，均有 $0\le l_i\le r_i\le 10^{18}$ 且 $l_i+t_i\le r_i$。

特殊性质 A：所有 $l_i=0$ 且整张图是一棵树。

特殊性质 B：所有 $t_i=1$。