문제
재원이의 마을에는 $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$번 정류장까지 가는 데에 걸리는 최소 시간을 재원이에게 알려주자.
출력
첫 번째 줄에 1ドル$번 정류장에서 $N$번 정류장까지 가는 데에 걸리는 최소 시간을 출력한다. 불가능한 경우에는 $-1$을 출력한다.
W3sicHJvYmxlbV9pZCI6IjMwODY5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZTY4XHViOWFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjN2FjXHVjNmQwXHVjNzc0XHVjNzU4IFx1YjljOFx1Yzc0NFx1YzVkMFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHViYzg0XHVjMmE0IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YWNmYyAkTSRcdWFjMWNcdWM3NTggXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiRpJFx1YmM4OCBcdWIxNzhcdWMxMjBcdWM3NDAgJHNfaSRcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NCAkdF9pJFx1YzJkY1x1YWMwNCBcdWQ2YzQgJGVfaSRcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3MCwgJHNfaSRcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVhY2ZjICRlX2kkXHViYzg4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViMmU0XHViOTc4IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YjI5NCBcdWJhNDhcdWNkOTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YmMzMFx1Y2MyOCBcdWFjMDRcdWFjYTkgJGdfaSRcdWFjMDAgXHVjNzg4XHVjNWI0ICQwJFx1YzJkY1x1YzVkMCAkc19pJFx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHViYzg0XHVjMmE0XHVhYzAwIFx1YzZiNFx1ZDU4OVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHViNGE0LCBcdWI5ZTQgJGdfaSRcdWMyZGNcdWFjMDRcdWI5YzhcdWIyZTQgJHNfaSRcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjIFx1YmM4NFx1YzJhNFx1YWMwMCBcdWM2YjRcdWQ1ODlcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJlNjhcdWI5YWMgXHViM2M0XHVjYzI5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM3YWNcdWM2ZDBcdWM3NzRcdWIyOTQsIDxzdHJvbmc+XHViZTY4XHViOWFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWUzMDxcL3N0cm9uZz5cdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHViZTY4XHViOWFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWUzMFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQsIFx1ZDYwNFx1YzdhYyBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHViMjk0IFx1YjE3OFx1YzEyMCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NCBcdWJjMzBcdWNjMjggXHVhYzA0XHVhY2E5XHVhY2ZjIFx1YmIzNFx1YWQwMFx1ZDU1OFx1YWM4YyBcdWM5YzBcdWFlMDggXHViMmY5XHVjN2E1IFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZTY4XHViOWFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWUzMFx1Yjk3YyBcdWNkNWNcdWIzMDAgJEskXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU3NCAkMSRcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjICROJFx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YjM3MFx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWM3YWNcdWM2ZDBcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjNTRjXHViODI0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHViOTU4XHVjN2E1XHVjNzU4IFx1YWMxY1x1YzIxOCAkTiQsIFx1YjE3OFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTggJE0kLCBcdWJlNjhcdWI5YWMgXHVhZTMwXHViMmU0XHViOWFjXHVhZTMwXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ2OWZcdWMyMTggJEskXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDIgXFxsZXEgTiBcXGxlcSA1MDA7JCAkMSBcXGxlcSBNIFxcbGVxIDI1MFxcLDAwMDskICQwIFxcbGVxIEsgXFxsZXEgNTAwKSQ8XC9wPlxyXG5cclxuPHA+JE0kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkaSsxJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJGkkXHViYzg4IFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NTggXHVjODE1XHViY2Y0ICRzX2kkLCAkZV9pJCwgJHRfaSQsICRnX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgc19pLCBlX2kgXFxsZXEgTjskICRzX2kgXFxuZXEgZV9pOyQgJDEgXFxsZXEgdF9pIFxcbGVxIDEwXFwsMDAwOyQgJDEgXFxsZXEgZ19pIFxcbGVxIDEwXFwsMDAwKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkMSRcdWJjODggXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjICROJFx1YmM4OCBcdWM4MTVcdWI5NThcdWM3YTVcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YjM3MFx1YzVkMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJC0xJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA4NjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXYWl0cyBGYXN0ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkphZXdvbiYjMzk7cyB0b3duIGhhcyAkTiQgYnVzIHN0b3BzIGFuZCAkTSQgYnVzIGxpbmVzLjxcL3A+XHJcblxyXG48cD5UaGUgJGkkdGggYnVzIGxpbmUgZGVwYXJ0cyBmcm9tIHRoZSAkc19pJC10aCBidXMgc3RvcCBhbmQgYXJyaXZlcyBhdCB0aGUgJGVfaSQtdGggYnVzIHN0b3AgYWZ0ZXIgJHRfaSQgdW5pdHMgb2YgdGltZS4gVGhlIGJ1cyBkb2VzIG5vdCBzdG9wIGF0IGFueSBzdG9wcyBvdGhlciB0aGFuICRzX2kkIGFuZCAkZV9pJC4gSW4gYWRkaXRpb24sIGEgbmV3IGJ1cyBkZXBhcnRzIGV2ZXJ5ICRnX2kkIHVuaXRzIG9mIHRpbWUuIFRoaXMgbWVhbnMgdGhhdCBhZnRlciB0aGUgZmlyc3QgYnVzIGRlcGFydHMgZnJvbSB0aGUgJHNfaSQtdGggYnVzIHN0b3AgYXQgdGltZSAkMCQsIGEgbmV3IGJ1cyBkZXBhcnRzIGZyb20gJHNfaSQgZXZlcnkgJGdfaSQgdW5pdHMgb2YgdGltZS48XC9wPlxyXG5cclxuPHA+SmFld29uIG5lZWRzIHRvIGFycml2ZSBhcyBmYXN0IGFzIGhlIGNhbiBhbmQgaGFzIGRlY2lkZWQgdG8gdXNlIHRoZSA8c3Ryb25nPldhaXRzIEZhc3RlcjxcL3N0cm9uZz4mbmJzcDtza2lsbC4gVXNpbmcgdGhpcywgaGUgY2FuIGltbWVkaWF0ZWx5IGRlcGFydCB1c2luZyBhbnkgYnVzIGxpbmUgc3RhcnRpbmcgYXQgdGhlIGN1cnJlbnQgc3RvcCwgcmVnYXJkbGVzcyBvZiB0aGUgd2FpdGluZyB0aW1lLjxcL3A+XHJcblxyXG48cD5MZXQmIzM5O3MgaGVscCBKYWV3b24gZmluZCB0aGUgc2hvcnRlc3QgdGltZSBpdCB0YWtlcyB0byB0cmF2ZWwgZnJvbSB0aGUgJDEkLXN0IGJ1cyBzdG9wIHRvIHRoZSAkTiQtdGggYnVzIHN0b3AgdXNpbmcgYSBtYXhpbXVtIG9mICRLJCBXYWl0cyBGYXN0ZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kLCAkTSQsIGFuZCAkSyQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgYnVzIHN0b3BzLCBidXMgbGluZXMsIGFuZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgV2FpdHMgRmFzdGVyIGFsbG93ZWQsIHJlc3BlY3RpdmVseS4gJCgyIFxcbGVxIE4gXFxsZXEgNTAwOyQgJDEgXFxsZXEgTSBcXGxlcSAyNTBcXCwwMDA7JCAkMCBcXGxlcSBLIFxcbGVxIDUwMCkkPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgbmV4dCAkTSQgbGluZXMsIGVhY2ggbGluZSBvZiBpbnB1dCBjb250YWlucyBpbmZvcm1hdGlvbiBhYm91dCB0aGUgYnVzIGxpbmVzLiBUaGUgJGkrMSQtdGggbGluZSBvZiBpbnB1dCBjb250YWlucyBmb3VyIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkc19pJCwgJGVfaSQsICR0X2kkLCBhbmQgJGdfaSQsIGRlbm90aW5nIGluZm9ybWF0aW9uIGFib3V0IHRoZSAkaSQtdGggYnVzIGxpbmUuICQoMSBcXGxlcSBzX2ksIGVfaSBcXGxlcSBOOyQgJHNfaSBcXG5lcSBlX2k7JCAkMSBcXGxlcSB0X2kgXFxsZXEgMTBcXCwwMDA7JCAkMSBcXGxlcSBnX2kgXFxsZXEgMTBcXCwwMDApJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgc2hvcnRlc3QgdGltZSBpdCB0YWtlcyB0byB0cmF2ZWwgZnJvbSB0aGUgJDEkLXN0IGJ1cyBzdG9wIHRvIHRoZSAkTiQtdGggYnVzIHN0b3AuIElmIG5vIHBhdGggZXhpc3RzLCBwcmludCAkLTEkIGluc3RlYWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==