시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjOWMwXHVjNmE5XHVjNzc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0IFx1YjBiNFx1YzVkMCBBXHVjNWQwXHVjMTFjIEIgXHVjOWMwXHVjODEwXHVhZTRjXHVjOWMwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWFjMDBcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBcdWM5YzBcdWM2YTlcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFlMzhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBLLCBOLCBNICgxICZsZTsgSyAmbGU7IDIwMDsgMiAmbGU7IE4gJmxlOyAyMDAwOyAxICZsZTsgTSAmbGU7IDEwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YmMxNFx1YjJmN1x1YWUzOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgQSwgQiwgdDxzdWI+aTxcL3N1Yj4sIGhpICgxICZsZTsgQSxCICZsZTsgTjsgMSAmbGU7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+OyAwICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAyMDApIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBBXHVjNjQwIEJcdWI5N2MgXHVjNzg3XHViMjk0IFx1YmMxNFx1YjJmN1x1YWUzOFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzAsIFx1Yzc3NCBcdWJjMTRcdWIyZjdcdWFlMzhcdWM3NDAgdDxzdWI+aTxcL3N1Yj5cdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YmE3MCBoPHN1Yj5pPFwvc3ViPiBcdWI5Y2NcdWQwN2MgXHViNWNmXHViYWE5XHVjNzQ0IFx1YWU0ZVx1YzU0NFx1YjBiNFx1YjliMFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBBICZuZTsgQlx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjNjNFx1Y2MyOVx1YzgxMFx1Yzc3OCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBLCBCICZsZTsgTjsgQSAmbmU7IEIpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWMwXHVjNmE5XHVjNzc0XHVhYzAwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBBXHVjNWQwXHVjMTFjIEJcdWM1ZDBcdWMxMWMgXHVkNTZkXHVkNTc0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YjU0YyBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0LCBcdWFkZjhcdWI3ZjQgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA3NzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb252ZXggSHVsbCIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB0cmF2ZWxsaW5nIG9uIGEgc2hpcCBpbiBhbiBhcmNoaXBlbGFnby4gVGhlIHNoaXAgaGFzIGEgY29udmV4IGh1bGwgd2hpY2ggaXMgSyBjZW50aW1ldHJlcyB0aGljay4gVGhlIGFyY2hpcGVsYWdvIGhhcyBOIGlzbGFuZHMsIG51bWJlcmVkIGZyb20gMSB0byBOLiBUaGVyZSBhcmUgTSBzZWEgcm91dGVzIGFtb25nc3QgdGhlbSwgd2hlcmUgdGhlIGl0aCByb3V0ZSBydW5zIGRpcmVjdGx5IGJldHdlZW4gdHdvIGRpZmZlcmVudCBpc2xhbmRzIGE8c3ViPmk8XC9zdWI+IGFuZCBiPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiAmbGU7IE4pLCB0YWtlcyB0PHN1Yj5pPFwvc3ViPiBtaW51dGVzIHRvIHRyYXZlbCBhbG9uZyBpbiBlaXRoZXIgZGlyZWN0aW9uLCBhbmQgaGFzIHJvY2tzIHRoYXQgd2VhciBkb3duIHRoZSBzaGlwJnJzcXVvO3MgaHVsbCBieSBoPHN1Yj5pPFwvc3ViPiBjZW50aW1ldHJlcy4gVGhlcmUgbWF5IGJlIG11bHRpcGxlIHJvdXRlcyBydW5uaW5nIGJldHdlZW4gYSBwYWlyIG9mIGlzbGFuZHMuPFwvcD5cclxuXHJcbjxwPllvdSB3b3VsZCBsaWtlIHRvIHRyYXZlbCBmcm9tIGlzbGFuZCBBIHRvIGEgZGlmZmVyZW50IGlzbGFuZCBCICgxICZsZTsgQSwgQiAmbGU7IE4pIGFsb25nIGEgc2VxdWVuY2Ugb2Ygc2VhIHJvdXRlcywgc3VjaCB0aGF0IHlvdXIgc2hpcCZyc3F1bztzIGh1bGwgcmVtYWlucyBpbnRhY3QgJm5kYXNoOyBpbiBvdGhlciB3b3Jkcywgc3VjaCB0aGF0IHRoZSBzdW0gb2YgdGhlIHJvdXRlcyZyc3F1bzsgaGkgdmFsdWVzIGlzIHN0cmljdGx5IGxlc3MgdGhhbiBLLjxcL3A+XHJcblxyXG48cD5BZGRpdGlvbmFsbHksIHlvdSBhcmUgaW4gYSBodXJyeSwgc28geW91IHdvdWxkIGxpa2UgdG8gbWluaW1pemUgdGhlIGFtb3VudCBvZiB0aW1lIG5lY2Vzc2FyeSB0byByZWFjaCBpc2xhbmQgQiBmcm9tIGlzbGFuZCBBLiBJdCBtYXkgbm90IGJlIHBvc3NpYmxlIHRvIHJlYWNoIGlzbGFuZCBCIGZyb20gaXNsYW5kIEEsIGhvd2V2ZXIsIGVpdGhlciBkdWUgdG8gaW5zdWZmaWNpZW50IHNlYSByb3V0ZXMgb3IgdGhlIGhhdmluZyB0aGUgc2hpcCZyc3F1bztzIGh1bGwgd2VhciBvdXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBLLCBOIGFuZCBNICgxICZsZTsgSyAmbGU7IDIwMCwgMiAmbGU7IE4gJmxlOyAyMDAwLCAxICZsZTsgTSAmbGU7IDEwMDAwKSwgZWFjaCBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBNIGxpbmVzIGVhY2ggY29udGFpbiA0IGludGVnZXJzIGE8c3ViPmk8XC9zdWI+IGI8c3ViPmk8XC9zdWI+IHQ8c3ViPmk8XC9zdWI+IGFuZCBoPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIDEgJmxlOyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPiwgMCAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMjAwKSwgZWFjaCBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLiBUaGUgaXRoIGxpbmUgaW4gdGhpcyBzZXQgb2YgTSBsaW5lcyBkZXNjcmliZXMgdGhlIGl0aCBzZWEgcm91dGUgKHdoaWNoIHJ1bnMgZnJvbSBpc2xhbmQgYTxzdWI+aTxcL3N1Yj4gdG8gaXNsYW5kIGI8c3ViPmk8XC9zdWI+LCB0YWtlcyB0PHN1Yj5pPFwvc3ViPiBtaW51dGVzIGFuZCB3ZWFycyBkb3duIHRoZSBzaGlwJnJzcXVvO3MgaHVsbCBieSBoPHN1Yj5pPFwvc3ViPiBjZW50aW1ldHJlcykuIE5vdGljZSB0aGF0IGE8c3ViPmk8XC9zdWI+ICZuZTsgYjxzdWI+aTxcL3N1Yj4gKHRoYXQgaXMsIHRoZSBlbmRzIG9mIGEgc2VhIHJvdXRlIGFyZSBkaXN0aW5jdCBpc2xhbmRzKS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEsIEIgJmxlOyBOOyBBICZuZTsgQiksIHRoZSBpc2xhbmRzIGJldHdlZW4gd2hpY2ggd2Ugd2FudCB0byB0cmF2ZWwuPFwvcD5cclxuXHJcbjxwPkZvciAyMCUgb2YgbWFya3MgZm9yIHRoaXMgcXVlc3Rpb24sIEsgPSAxIGFuZCBOICZsZTsgMjAwLiBGb3IgYW5vdGhlciAyMCUgb2YgdGhlIG1hcmtzIGZvciB0aGlzIHByb2JsZW0sIEsgPSAxIGFuZCBOICZsZTsgMjAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgaW50ZWdlcjogdGhlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBtaW5pbWFsIHRpbWUgcmVxdWlyZWQgdG8gdHJhdmVsIGZyb20gQSB0byBCIHdpdGhvdXQgd2VhcmluZyBvdXQgdGhlIHNoaXAmcnNxdW87cyBodWxsLCBvciAmbWludXM7MSB0byBpbmRpY2F0ZSB0aGF0IHRoZXJlIGlzIG5vIHdheSB0byB0cmF2ZWwgZnJvbSBBIHRvIEIgd2l0aG91dCB3ZWFyaW5nIG91dCB0aGUgc2hpcCZyc3F1bztzIGh1bGwuPFwvcD5cclxuIiwiaGludCI6IjxwPkV4cGxhbmF0aW9uIG9mIE91dHB1dCBmb3IgU2FtcGxlIElucHV0IDE8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggb2YgbGVuZ3RoIDEgZnJvbSAxIHRvIDQgd291bGQgd2VhciBvdXQgdGhlIGh1bGwgb2YgdGhlIHNoaXAuIFRoZSB0aHJlZSBwYXRocyBvZiBsZW5ndGggMiAoWzEsIDIsIDRdIGFuZCBbMSwgMywgNF0gdHdvIGRpZmZlcmVudCB3YXlzKSB0YWtlIGF0IGxlYXN0IDggbWludXRlcy4gVGhlIHBhdGggWzEsIDIsIDMsIDRdIHRha2VzIDcgbWludXRlcyBhbmQgb25seSB3ZWFycyBkb3duIHRoZSBodWxsIGJ5IDcgY2VudGltZXRyZXMsIHdoZXJlYXMgdGhlIHBhdGggWzEsIDMsIDIsIDRdIHRha2VzIDEzIG1pbnV0ZXMgYW5kIHdlYXJzIGRvd24gdGhlIGh1bGwgYnkgNSBjZW50aW1ldHJlcy48XC9wPlxyXG5cclxuPHA+RXhwbGFuYXRpb24gb2YgT3V0cHV0IGZvciBTYW1wbGUgSW5wdXQgMjxcL3A+XHJcblxyXG48cD5UaGUgZGlyZWN0IHBhdGggWzEsIDNdIHdlYXJzIGRvd24gdGhlIGh1bGwgdG8gMCwgYXMgZG9lcyB0aGUgcGF0aCBbMSwgMiwgM10uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=