빨리 기다리기

면접 대비

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

요약

버스를 기다리지 않고 바로 출발시키는 기능을 최대 K번 쓸 때, 정류장 1에서 N까지 가는 최소 시간을 구합니다.

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

문제

재원이의 마을에는 $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
```