빨리 기다리기

시간 제한2초메모리 제한1024 MB

요약

배차 간격을 무시하고 최대 K번 버스를 즉시 출발시킬 수 있을 때 1번 정류장에서 N번 정류장까지의 최소 이동 시간을 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 최단 경로, 동적 계획법, 힙
정답자: 아직 제출이 없습니다

문제

재원이의 마을에는 $N$ 개의 버스 정류장과 $M$ 개의 버스 노선이 있다.

$i$ 번 노선은 $s\_i$ 번 정류장에서 출발해 $t\_i$ 시간 후 $e\_i$ 번 정류장에 도착하며, $s\_i$ 번 정류장과 $e\_i$ 번 정류장을 제외한 다른 정류장에는 멈추지 않는다. 또한, 배차 간격 $g\_i$ 가 있어 $0$ 시에 $s\_i$ 번 정류장에서 버스가 운행을 시작한 뒤, 매 $g\_i$ 시간마다 $s\_i$ 번 정류장에서 버스가 운행을 시작한다.

빨리 도착해야 하는 재원이는, 빨리 기다리기를 사용하기로 했다. 빨리 기다리기를 사용하면, 현재 정류장에서 출발하는 노선 중 하나를 선택해 배차 간격과 무관하게 지금 당장 출발하도록 할 수 있다.

빨리 기다리기를 최대 $K$ 번 사용해 $1$ 번 정류장에서 $N$ 번 정류장까지 가는 데에 걸리는 최소 시간을 재원이에게 알려주자.

입력

첫 번째 줄에 정류장의 개수 $N$ , 노선의 개수 $M$ , 빨리 기다리기를 사용할 수 있는 최대 횟수 $K$ 가 공백으로 구분되어 주어진다. $(2 \leq N \leq 500;$ $1 \leq M \leq 250\\,000;$ $0 \leq K \leq 500)$

$M$ 개의 줄에 걸쳐 버스 노선의 정보가 주어진다. $i+1$ 번째 줄에는 $i$ 번 버스 노선의 정보 $s\_i$ , $e\_i$ , $t\_i$ , $g\_i$ 가 공백으로 구분되어 주어진다. $(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)$

출력

첫 번째 줄에 $1$ 번 정류장에서 $N$ 번 정류장까지 가는 데에 걸리는 최소 시간을 출력한다. 불가능한 경우에는 $-1$ 을 출력한다.

예제1

예제 1
입력
```
3 3 1
1 3 7 2
1 2 2 5
2 3 4 4
```
예상 출력
```
6
```