시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 140 57 30 47.619%

문제

사회에 불만이 많은 지용이는 미적분학 교과서를 적당히 찢어서, 한 사람이 충분히 탈 만한 두께 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을 출력한다.

예제 입력 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

예제 출력 1

7

예제 입력 2

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

예제 출력 2

-1
W3sicHJvYmxlbV9pZCI6IjEwNzc2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODFjXHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYWNcdWQ2OGNcdWM1ZDAgXHViZDg4XHViOWNjXHVjNzc0IFx1YjljZVx1Yzc0MCBcdWM5YzBcdWM2YTlcdWM3NzRcdWIyOTQgXHViYmY4XHVjODAxXHViZDg0XHVkNTU5IFx1YWQ1MFx1YWNmY1x1YzExY1x1Yjk3YyBcdWM4MDFcdWIyZjlcdWQ3ODggXHVjYzIyXHVjNWI0XHVjMTFjLCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWQwYzggXHViOWNjXHVkNTVjIFx1YjQ1MFx1YWVkOCBLXHVjNzU4IFx1YjVjZlx1YmFhOVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzZhOVx1Yzc3NFx1YjI5NCBcdWM3NzRcdWM4MWMgQSBcdWQ1NmRcdWFkNmNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTc0XHVjMTFjIFx1YmIzNFx1Yzc3OFx1YjNjNCBCXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM4MWNcdWFkNmRcdWM3NDQgXHVhYzc0XHVjMTI0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJhNDBcdWFjZTAgXHViYTNjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI1YTBcdWIwYTAgXHVhY2M0XHVkNjhkXHVjNzc0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOLCBBICZuZTsgQik8XC9wPlxyXG5cclxuPHA+XHViYzE0XHViMmU0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMTJjXHVjNzc0IFx1Yzc4OFx1YWNlMCBNXHVhYzFjXHVjNzU4IFx1YmMxNFx1YjJmN1x1YWUzOFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmMxNFx1YjJmN1x1YWUzOCBcdWM2NzhcdWM3NTggXHVhZTM4XHViODVjXHViMjk0IFx1YWMwOCBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNzNjXHViYTcwIFx1YzljMFx1YzZhOVx1Yzc3NFx1YjI5NCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YjNkOVx1YzU0OCBcdWMxMmNcdWI0ZTRcdWM3NDQgXHVhYzcwXHVjY2QwXHVhYzAwXHViYTc0XHVjMTFjIFx1ZDU2ZFx1ZDU3NFx1ZDU2MCBcdWFjYzRcdWQ2OGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWJjMTRcdWIyZjdcdWFlMzhcdWM3NDAgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0IHRpLCBcdWI1Y2ZcdWJhYTlcdWM3NDQgXHVhZTRlXHVjNTQ0XHViMGI0XHViOWFjXHViMjk0IFx1YzgxNVx1YjNjNCBoPHN1Yj5pPFwvc3ViPiAoY20pIFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWI1Y2ZcdWJhYTlcdWM3NzQgMGNtIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWI0NTBcdWFlZDhcdWI5N2MgXHVhYzAwXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNFx1YmE3NCAtIFx1YjJlY1x1YjlhYyBcdWI5ZDBcdWQ1NzRcdWMxMWMgXHVhY2JkXHViODVjIFx1YzBjMVx1Yzc1OCBoPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWQ1NjlcdWM3NzQgSyBcdWM3NzRcdWMwYzFcdWM3NzQgXHViNDFjXHViMmU0XHViYTc0LCBcdWMyMThcdWM2MDFcdWM3NDQgXHViYWJiXHVkNTU4XHViMjk0IFx1YzljMFx1YzZhOVx1Yzc3NFx1Yzc1OCBcdWJhYTlcdWMyMjhcdWM3NDQgXHViY2Y0XHVjN2E1XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU2MFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQoISk8XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVjNmE5XHVjNzc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0IFx1YjBiNFx1YzVkMCBBXHVjNWQwXHVjMTFjIEIgXHVjOWMwXHVjODEwXHVhZTRjXHVjOWMwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWFjMDBcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBcdWM5YzBcdWM2YTlcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFlMzhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IEssIE4sIE0gKDEgJmxlOyBLICZsZTsgMjAwOyAyICZsZTsgTiAmbGU7IDIwMDA7IDEgJmxlOyBNICZsZTsgMTAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1ZDZjNCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHViYzE0XHViMmY3XHVhZTM4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBBLCBCLCB0PHN1Yj5pPFwvc3ViPiwgaGkgKDEgJmxlOyBBLEIgJmxlOyBOOyAxICZsZTsgdDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+NTxcL3N1cD47IDAgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDIwMCkgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IEFcdWM2NDAgQlx1Yjk3YyBcdWM3ODdcdWIyOTQgXHViYzE0XHViMmY3XHVhZTM4XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCwgXHVjNzc0IFx1YmMxNFx1YjJmN1x1YWUzOFx1Yzc0MCB0PHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWFjXHViYTcwIGg8c3ViPmk8XC9zdWI+IFx1YjljY1x1ZDA3YyBcdWI1Y2ZcdWJhYTlcdWM3NDQgXHVhZTRlXHVjNTQ0XHViMGI0XHViOWIwXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIEEgJm5lOyBCXHVjNzg0XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHViM2M0XHVjYzI5XHVjODEwXHVjNzc4IEEsIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOOyBBICZuZTsgQik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5YzBcdWM2YTlcdWM3NzRcdWFjMDAgXHVjNTQ4XHVjODA0XHVkNTU4XHVhYzhjIEFcdWM1ZDBcdWMxMWMgQlx1YzVkMFx1YzExYyBcdWQ1NmRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWFkZjggXHViNTRjIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQsIFx1YWRmOFx1YjdmNCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDc3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbnZleCBIdWxsIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHRyYXZlbGxpbmcgb24gYSBzaGlwIGluIGFuIGFyY2hpcGVsYWdvLiBUaGUgc2hpcCBoYXMgYSBjb252ZXggaHVsbCB3aGljaCBpcyBLIGNlbnRpbWV0cmVzIHRoaWNrLiBUaGUgYXJjaGlwZWxhZ28gaGFzIE4gaXNsYW5kcywgbnVtYmVyZWQgZnJvbSAxIHRvIE4uIFRoZXJlIGFyZSBNIHNlYSByb3V0ZXMgYW1vbmdzdCB0aGVtLCB3aGVyZSB0aGUgaXRoIHJvdXRlIHJ1bnMgZGlyZWN0bHkgYmV0d2VlbiB0d28gZGlmZmVyZW50IGlzbGFuZHMgYTxzdWI+aTxcL3N1Yj4gYW5kIGI8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+ICZsZTsgTiksIHRha2VzIHQ8c3ViPmk8XC9zdWI+IG1pbnV0ZXMgdG8gdHJhdmVsIGFsb25nIGluIGVpdGhlciBkaXJlY3Rpb24sIGFuZCBoYXMgcm9ja3MgdGhhdCB3ZWFyIGRvd24gdGhlIHNoaXAmcnNxdW87cyBodWxsIGJ5IGg8c3ViPmk8XC9zdWI+IGNlbnRpbWV0cmVzLiBUaGVyZSBtYXkgYmUgbXVsdGlwbGUgcm91dGVzIHJ1bm5pbmcgYmV0d2VlbiBhIHBhaXIgb2YgaXNsYW5kcy48XC9wPlxyXG5cclxuPHA+WW91IHdvdWxkIGxpa2UgdG8gdHJhdmVsIGZyb20gaXNsYW5kIEEgdG8gYSBkaWZmZXJlbnQgaXNsYW5kIEIgKDEgJmxlOyBBLCBCICZsZTsgTikgYWxvbmcgYSBzZXF1ZW5jZSBvZiBzZWEgcm91dGVzLCBzdWNoIHRoYXQgeW91ciBzaGlwJnJzcXVvO3MgaHVsbCByZW1haW5zIGludGFjdCAmbmRhc2g7IGluIG90aGVyIHdvcmRzLCBzdWNoIHRoYXQgdGhlIHN1bSBvZiB0aGUgcm91dGVzJnJzcXVvOyBoaSB2YWx1ZXMgaXMgc3RyaWN0bHkgbGVzcyB0aGFuIEsuPFwvcD5cclxuXHJcbjxwPkFkZGl0aW9uYWxseSwgeW91IGFyZSBpbiBhIGh1cnJ5LCBzbyB5b3Ugd291bGQgbGlrZSB0byBtaW5pbWl6ZSB0aGUgYW1vdW50IG9mIHRpbWUgbmVjZXNzYXJ5IHRvIHJlYWNoIGlzbGFuZCBCIGZyb20gaXNsYW5kIEEuIEl0IG1heSBub3QgYmUgcG9zc2libGUgdG8gcmVhY2ggaXNsYW5kIEIgZnJvbSBpc2xhbmQgQSwgaG93ZXZlciwgZWl0aGVyIGR1ZSB0byBpbnN1ZmZpY2llbnQgc2VhIHJvdXRlcyBvciB0aGUgaGF2aW5nIHRoZSBzaGlwJnJzcXVvO3MgaHVsbCB3ZWFyIG91dC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEssIE4gYW5kIE0gKDEgJmxlOyBLICZsZTsgMjAwLCAyICZsZTsgTiAmbGU7IDIwMDAsIDEgJmxlOyBNICZsZTsgMTAwMDApLCBlYWNoIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE0gbGluZXMgZWFjaCBjb250YWluIDQgaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gYjxzdWI+aTxcL3N1Yj4gdDxzdWI+aTxcL3N1Yj4gYW5kIGg8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+ICZsZTsgTiwgMSAmbGU7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+LCAwICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAyMDApLCBlYWNoIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UuIFRoZSBpdGggbGluZSBpbiB0aGlzIHNldCBvZiBNIGxpbmVzIGRlc2NyaWJlcyB0aGUgaXRoIHNlYSByb3V0ZSAod2hpY2ggcnVucyBmcm9tIGlzbGFuZCBhPHN1Yj5pPFwvc3ViPiB0byBpc2xhbmQgYjxzdWI+aTxcL3N1Yj4sIHRha2VzIHQ8c3ViPmk8XC9zdWI+IG1pbnV0ZXMgYW5kIHdlYXJzIGRvd24gdGhlIHNoaXAmcnNxdW87cyBodWxsIGJ5IGg8c3ViPmk8XC9zdWI+IGNlbnRpbWV0cmVzKS4gTm90aWNlIHRoYXQgYTxzdWI+aTxcL3N1Yj4gJm5lOyBiPHN1Yj5pPFwvc3ViPiAodGhhdCBpcywgdGhlIGVuZHMgb2YgYSBzZWEgcm91dGUgYXJlIGRpc3RpbmN0IGlzbGFuZHMpLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSwgQiAmbGU7IE47IEEgJm5lOyBCKSwgdGhlIGlzbGFuZHMgYmV0d2VlbiB3aGljaCB3ZSB3YW50IHRvIHRyYXZlbC48XC9wPlxyXG5cclxuPHA+Rm9yIDIwJSBvZiBtYXJrcyBmb3IgdGhpcyBxdWVzdGlvbiwgSyA9IDEgYW5kIE4gJmxlOyAyMDAuIEZvciBhbm90aGVyIDIwJSBvZiB0aGUgbWFya3MgZm9yIHRoaXMgcHJvYmxlbSwgSyA9IDEgYW5kIE4gJmxlOyAyMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG1pbmltYWwgdGltZSByZXF1aXJlZCB0byB0cmF2ZWwgZnJvbSBBIHRvIEIgd2l0aG91dCB3ZWFyaW5nIG91dCB0aGUgc2hpcCZyc3F1bztzIGh1bGwsIG9yICZtaW51czsxIHRvIGluZGljYXRlIHRoYXQgdGhlcmUgaXMgbm8gd2F5IHRvIHRyYXZlbCBmcm9tIEEgdG8gQiB3aXRob3V0IHdlYXJpbmcgb3V0IHRoZSBzaGlwJnJzcXVvO3MgaHVsbC48XC9wPlxyXG4iLCJoaW50IjoiPHA+RXhwbGFuYXRpb24gb2YgT3V0cHV0IGZvciBTYW1wbGUgSW5wdXQgMTxcL3A+XHJcblxyXG48cD5UaGUgcGF0aCBvZiBsZW5ndGggMSBmcm9tIDEgdG8gNCB3b3VsZCB3ZWFyIG91dCB0aGUgaHVsbCBvZiB0aGUgc2hpcC4gVGhlIHRocmVlIHBhdGhzIG9mIGxlbmd0aCAyIChbMSwgMiwgNF0gYW5kIFsxLCAzLCA0XSB0d28gZGlmZmVyZW50IHdheXMpIHRha2UgYXQgbGVhc3QgOCBtaW51dGVzLiBUaGUgcGF0aCBbMSwgMiwgMywgNF0gdGFrZXMgNyBtaW51dGVzIGFuZCBvbmx5IHdlYXJzIGRvd24gdGhlIGh1bGwgYnkgNyBjZW50aW1ldHJlcywgd2hlcmVhcyB0aGUgcGF0aCBbMSwgMywgMiwgNF0gdGFrZXMgMTMgbWludXRlcyBhbmQgd2VhcnMgZG93biB0aGUgaHVsbCBieSA1IGNlbnRpbWV0cmVzLjxcL3A+XHJcblxyXG48cD5FeHBsYW5hdGlvbiBvZiBPdXRwdXQgZm9yIFNhbXBsZSBJbnB1dCAyPFwvcD5cclxuXHJcbjxwPlRoZSBkaXJlY3QgcGF0aCBbMSwgM10gd2VhcnMgZG93biB0aGUgaHVsbCB0byAwLCBhcyBkb2VzIHRoZSBwYXRoIFsxLCAyLCAzXS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==