Fast Waiting

Interview

Time limit2sMemory limit1024 MB

Summary

Find the minimum time from stop 1 to stop N when Jaewon can make up to K routes depart immediately instead of waiting for their next scheduled bus.

Level: Medium6 of 10
Topics: Graph, Shortest path, Dynamic programming
Solved: No attempts yet

Problem

Jaewon's town has $N$ bus stops and $M$ bus routes.

Route $i$ departs from stop $s_i$ and arrives at stop $e_i$ after $t_i$ hours. It does not stop at any other stop. Route $i$ has a dispatch interval $g_i$ : a bus leaves stop $s_i$ at hour 0, and then again every $g_i$ hours.

Jaewon is in a hurry, so he can use fast waiting. With fast waiting, he picks a route that departs from his current stop and makes it leave right now, regardless of its dispatch interval.

Find the minimum time for Jaewon to go from stop 1 to stop $N$ when he uses fast waiting at most $K$ times.

Input

The first line contains $N$ , $M$ , and $K$ , the number of stops, the number of routes, and the maximum number of fast waiting uses, separated by spaces. $(2 \leq N \leq 500;$ $1 \leq M \leq 250\,000;$ $0 \leq K \leq 500)$

Each of the next $M$ lines contains $s_i$ , $e_i$ , $t_i$ , and $g_i$ for route $i$ , separated by spaces. $(1 \leq s_i, e_i \leq N;$ $s_i \neq e_i;$ $1 \leq t_i \leq 10\,000;$ $1 \leq g_i \leq 10\,000)$

Output

Print the minimum time to go from stop 1 to stop $N$ on the first line. If it is impossible, print $-1$ .

Examples1

Example 1
Input
```
3 3 1
1 3 7 2
1 2 2 5
2 3 4 4
```
Expected output
```
6
```