时空限制

2.5S/512M

题目描述

有 $n$ 个站点，编号 $1\sim n$。还有 $m$ 条公交路线，$i$ 号公交路线的首次发车时间为 $a_i$，每辆车从站点 $u_i$ 出发经过 $t_i$ 时间到达站点 $v_i$。

所有公交路线都是间隔 $k$ 时间发车，也就是说对于 $i$ 号公交路线，会分别在时间 $a_i,a_i+k,a_i+2\times k,a_i+3\times k,\dots$ 发车。

现在时间为 $0$，你位于站点 $1$，要前往站点 $n$。过程中可以选择在站点等待下次发车，但是由于车上有空调而站点没有空调，所以你希望尽可能减少在站点等待的时间。

求在站点等待的总时间之和的最小值。

格式

输入格式

第一行包含三个整数 $n,m,k$，分别表示站点的数量、公交路线的数量以及发车时间的间隔。

接下来 $m$ 行每行包含四个整数 $a_i,u_i,v_i,t_i$，表示一条首次发车时间为 $a_i$，每辆车从站点 $u_i$ 出发经过 $t_i$ 时间到达站点 $v_i$ 的公交路线。

输出格式

输出一个整数表示在站点等待的总时间之和的最小值。保证存在从站点 $1$ 出发到达站点 $n$ 的方案。

样例

样例输入 #1

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

样例输出 #1

5

样例解释 #1

以下为其中一种在站点等待的总时间之和最小的方案：在站点 $1$ 等待到时间 $4$，坐 $2$ 号公交在时间 $8$ 到达站点 $2$，坐 $1$ 号公交在时间 $13$ 到达站点 $3$，坐 $6$ 号公交在时间 $19$ 到达站点 $2$，在站点 $2$ 等待到时间 $20$，坐 $5$ 号公交在时间 $28$ 到达站点 $4$。

在站点等待的总时间之和为 $4+0+0+1=5$。

数据规模

对于 $30\%$ 的数据，$k\leq 10$。

另有 $30\%$ 的数据，$m\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^4$，$1\leq m\leq 3\times 10^5$，$1\leq k\leq 10^6$，$0\leq a_i<k$，$1\leq u_i,v_i\leq n$，$1\leq t_i\leq 10^9$。数据保证存在从站点 $1$ 出发到达站点 $n$ 的方案，可能存在重边或者自环。