题目描述

JOI 王国由 $N$ 个城市组成，这些城市被编号为 1 至 $N$。JOI 王国内有 $M$ 条单向高速公路，这些高速公路被编号为 1 至 $M$。通过高速公路 $i$（$1 \le i \le M$），可以从城市 $A_i$ 移动到城市 $B_i$，所需时间为 $L_i$。

每次通过高速公路都会产生通行费。高速公路 $i$ 的基本通行费为 $C_i$，但由于 JOI 王国的劳动者厌恶加班，若离开基准时刻 0 的时间越久，通行费就会越高。具体而言，若在时刻 $t$ 从城市 $A_i$ 出发并通过高速公路 $i$，则通行费可表示为 $C_i + K \times |t|$，其中 $|t|$ 表示 $t$ 的绝对值。

你居住在城市 1，计划前往朋友居住的城市 $N$。你希望确认是否可以通过高速公路从城市 1 移动到城市 $N$，若可能，则进一步求出通行费总和的最小值。你可以自由选择移动路径和在各城市出发的时间。特别地，允许在负时刻从城市 1 出发，也允许在途中某个城市停留一段时间。

给定高速公路的信息以及常数 $K$，请编写一个程序，判断是否可以通过高速公路从城市 1 移动到城市 $N$，若可以，则求出通行费总和的最小值。

此外，在本题的约束条件下，若可以通过高速公路从城市 1 移动到城市 $N$，则通行费总和的最小值必定为整数。

输入格式

输入以如下格式给出。

$N$ $M$ $K$

$A_1$ $B_1$ $L_1$ $C_1$ $A_2$ $B_2$ $L_2$ $C_2$

⋮

$A_M$ $B_M$ $L_M$ $C_M$

输出格式

若无法通过高速公路从城市 1 移动到城市 $N$，则输出 −1。若可以，则输出一行整数，表示通行费总和的最小值。

样例

样例输入 1

4 4 2
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3

样例输出 1

15

样例输入 2

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

样例输出 2

9

样例输入 3

2 1 10
2 1 4 7

样例输出 3

-1

样例输入 4

4 3 5
1 2 3 1
2 3 1 10
3 4 7 6

样例输出 4

37

样例输入 5

8 8 2
1 2 1 5
5 6 3 1
2 4 10 18
3 5 3 1
1 3 4 2
5 6 2 2
2 5 2 3
6 8 1 1

样例输出 5

25

样例输入 6

6 10 100000
4 2 212037 752027141
2 5 667097 1571491
2 1 769275 576006950
1 2 711969 526189398
5 3 733555 206320177
3 4 364807 802102091
1 4 467240 183184247
3 5 44994 15991843
5 3 613192 782356546
4 6 832593 639529758

样例输出 6

47546714005

数据范围

$2 \le N \le 4000$。

$1 \le M \le 8000$。

$0 \le K \le 100000$。

$1 \le A_i \le N$（$1 \le i \le M$）。

$1 \le B_i \le N$（$1 \le i \le M$）。

$A_i \ne B_i$（$1 \le i \le M$）。

$1 \le L_i \le 1000000$（$1 \le i \le M$）。

$0 \le C_i \le 10^9$（$1 \le i \le M$）。

所有输入的值均为整数。

本题共 20 个测试点，每个测试点 5 分，合计 100 分。

测试点编号	测试点数	数据范围
1 ~ 2	2	$N \le 100$，$M \le 200$，$K = 0$
3 ~ 6	4	$N \le 100$，$M \le 200$，$L_i \le 20$（$1 \le i \le M$）
7 ~ 9	3	$N \le 100$，$M = N - 1$，$A_i = i$，$B_i = i + 1$（$1 \le i \le M$）
10 ~ 14	5	$N \le 100$，$M \le 200$，$N$ 为偶数且 $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$
15 ~ 17	3	$N \le 100$，$M \le 200$
18 ~ 19	2	$N \le 1500$，$M \le 3000$
20	1	无额外约束