시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 121 40 17 34.694%

문제

사회에 불만이 많은 지용이는 미적분학 교과서를 적당히 찢어서, 한 사람이 충분히 탈 만한 두께 K의 뗏목을 만들었다.

지용이는 이제 A 항구에서 출발해서 무인도 B에 자신의 제국을 건설하기 위해 멀고 먼 여행을 떠날 계획이다. (1 ≤ A, B ≤ N, A ≠ B)

바다에는 N개의 섬이 있고 M개의 바닷길이 있으며, 바닷길 외의 길로는 갈 수가 없으며 지용이는 A에서 B로 가는 동안 섬들을 거쳐가면서 항해할 계획이다.

각 바닷길은 지나가는 데 걸리는 시간 ti, 뗏목을 깎아내리는 정도 hi (cm) 를 가지고 있으며, 만약에 도착하기 전에 뗏목이 0cm 이하의 두께를 가지게 된다면 - 달리 말해서 경로 상의 hi의 합이 K 이상이 된다면, 수영을 못하는 지용이의 목숨을 보장하지 못할수도 있다(!)

지용이는 가장 빠른 시간 내에 A에서 B 지점까지 안전하게 가기를 원한다. 지용이를 도와 그러한 길의 길이를 출력해주자.

입력

첫번째 줄에는 정수 K, N, M (1 ≤ K ≤ 200; 2 ≤ N ≤ 2000; 1 ≤ M ≤ 10000)이 주어진다.

이 후 M개의 줄에 각 바닷길의 정보가 A, B, ti, hi (1 ≤ A,B ≤ N; 1 ≤ ti ≤ 105; 0 ≤ hi ≤ 200) 형태로 주어진다. 이는 A와 B를 잇는 바닷길이 존재하며, 이 바닷길은 ti의 시간이 걸리며 hi 만큼 뗏목을 깎아내린다는 것을 의미한다. A ≠ B임이 보장된다.

마지막 줄에는 시작점과 도착점인 A, B가 주어진다. (1 ≤ A, B ≤ N; A ≠ B)

출력

지용이가 안전하게 A에서 B에서 항해할 수 있다면 그 때 걸리는 시간을, 그럴 수 없다면 -1을 출력한다.

예제 입력

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

예제 출력

7

예제 입력 2

3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3

예제 출력 2

-1

힌트