说明

探险者需要穿越一个充满时空裂隙的迷宫，共包含有 $n$ 个时空裂隙（简称结点），编号为 $1 \sim n$，探险者可以在结点任意停留。在时空裂隙之间存在着 $m$ 条路径，每条路径可以描述为 $(u_i, v_i, w_i, s_i, e_i)$ 表示从结点 $u_i$ 到结点 $v_i$ 存在着一条双向路径，通过这条路径需要耗时 $w_i$，且只有当前时刻位于 $[s_i, e_i]$ 的区间才可以进入这条路径并通过（因此经过这条路径到达 $v_i$ 的时刻必然在 $[s_i + w_i, e_i + w_i]$ 区间内）。

同时，探险者有调整时间流速的机会：即可以在某一次通过路径时忽略 $[s_i, e_i]$ 的时间限制，这样的技能最多使用 $k$ 次。

初始时，探险者在 $1$ 号结点，初始时刻为 $0$。请问从结点 $1$ 到达结点 $n$，需要消耗的最短时间是多少？

输入格式

输入的第一行包含三个整数 $n, m, k$，相邻整数之间使用一个空格分隔。

接下来 $m$ 行，每行包含五个整数 $u_i, v_i, w_i, s_i, e_i$，相邻整数之间使用一个空格分隔，表示第 $i$ 条路径的信息。图中可能出现重边和自环。

输出格式

输出一行包含一个整数表示答案，如果不存在可能的路径，输出整数 $-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

提示

样例说明

对于样例 1：可以直接走 $1 \to 3$ 这条路径，耗时为 6；走 $1 \to 2 \to 3$ 耗时为 8，因为到达 2 之后需要等到时间 5 才可以继续前进。

对于样例 2：由于有一次释放技能的机会，先走 $1 \to 2$，然后使用一次技能从 $2 \to 3$，总耗时为 4。

评测用例规模与约定

对于 $10\%$ 的评测用例，$2 \le n \le 5$；

对于 $20\%$ 的评测用例，$2 \le n \le 10$；

对于 $40\%$ 的评测用例，$2 \le n \le 100$；

对于 $60\%$ 的评测用例，$2 \le n \le 1000$；

对于 $80\%$ 的评测用例，$2 \le n \le 10000$；

对于所有评测用例，$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$。