문제
은하는 열심히 일한 덕에 드디어 새 차를 뽑았습니다! 시운전으로 일직선 도로를 따라 차를 타고 목적지로 이동하려 합니다. 목적지까지 거리가 꽤 되기 때문에, 중간중간 주유소에서 연료를 넣으려고 합니다. 시운전 중에는 다음과 같은 조건을 지켜야 합니다.
- $i$번째 주유소는 길의 원점으로부터 오른쪽으로 $x_{i}$킬로미터 떨어진 위치에 있으며, 이 주유소에서 차에 넣을 수 있는 연료는 리터 당 단가가 $p_{i}$이고 총 $a_{i}$리터만큼의 연료가 있습니다.
- 주유소에서는 연료를 $a_{i}$리터 이하로 원하는 만큼 주유할 수 있습니다.
- 각 주유소에서 주유한 뒤 차에 들어 있는 연료의 양이 차의 연료 용량인 $F$리터를 넘겨서는 안 됩니다.
- 차는 1ドル$리터의 연료로 1ドル$킬로미터를 움직일 수 있습니다.
- 새 차는 시운전 전에는 연료가 없습니다. 따라서 차의 시작 지점은 첫 번째 주유소입니다.
- 목적지는 길의 원점으로부터 오른쪽으로 $X$킬로미터 떨어진 위치입니다.
은하는 열심히 번 돈을 연료에 쓰는 것은 아까워, 목적지까지 최소 비용으로 이동하려 합니다. 여러분은 은하를 도와 주어야 합니다!
출력
어떤 경로로 시운전을 진행해도 목적지에 도달할 수 없으면 첫째 줄에 -1을 출력합니다. 그렇지 않으면 첫째 줄에 시운전을 마치는 데 드는 최소 비용을 출력합니다.
W3sicHJvYmxlbV9pZCI6IjMxMzk4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzAwXHVjMmE0IFx1Y2RhOVx1YzgwNFx1YzE4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzQwXHVkNTU4XHViMjk0IFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWM3N2NcdWQ1NWMgXHViMzU1XHVjNWQwIFx1YjRkY1x1YjUxNFx1YzViNCBcdWMwYzggXHVjYzI4XHViOTdjIFx1YmY1MVx1YzU1OFx1YzJiNVx1YjJjOFx1YjJlNCEgXHVjMmRjXHVjNmI0XHVjODA0XHVjNzNjXHViODVjIFx1Yzc3Y1x1YzljMVx1YzEyMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViNTMwXHViNzdjIFx1Y2MyOFx1Yjk3YyBcdWQwYzBcdWFjZTAgXHViYWE5XHVjODAxXHVjOWMwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjgyNCBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YmFhOVx1YzgwMVx1YzljMFx1YWU0Y1x1YzljMCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVhZjY0IFx1YjQxOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzkxMVx1YWMwNFx1YzkxMVx1YWMwNCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM1ZDBcdWMxMWMgXHVjNWYwXHViOGNjXHViOTdjIFx1YjEyM1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YzJkY1x1YzZiNFx1YzgwNCBcdWM5MTFcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHVjOWMwXHVjZjFjXHVjNTdjIFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kaSRcdWJjODhcdWM5ZjggXHVjOGZjXHVjNzIwXHVjMThjXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWM2ZDBcdWM4MTBcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjICR4X3tpfSRcdWQwYWNcdWI4NWNcdWJiZjhcdWQxMzAgXHViNWE4XHVjNWI0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc3NCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM1ZDBcdWMxMWMgXHVjYzI4XHVjNWQwIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YjhjY1x1YjI5NCBcdWI5YWNcdWQxMzAgXHViMmY5IFx1YjJlOFx1YWMwMFx1YWMwMCAkcF97aX0kXHVjNzc0XHVhY2UwIFx1Y2QxZCAkYV97aX0kXHViOWFjXHVkMTMwXHViOWNjXHVkMDdjXHVjNzU4IFx1YzVmMFx1YjhjY1x1YWMwMCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzhmY1x1YzcyMFx1YzE4Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWM1ZjBcdWI4Y2NcdWI5N2MgJGFfe2l9JFx1YjlhY1x1ZDEzMCBcdWM3NzRcdWQ1NThcdWI4NWMgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWM4ZmNcdWM3MjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YzhmY1x1YzcyMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWM4ZmNcdWM3MjBcdWQ1NWMgXHViNGE0IFx1Y2MyOFx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzVmMFx1YjhjY1x1Yzc1OCBcdWM1OTFcdWM3NzQgXHVjYzI4XHVjNzU4IFx1YzVmMFx1YjhjYyBcdWM2YTlcdWI3YzlcdWM3NzggJEYkXHViOWFjXHVkMTMwXHViOTdjIFx1YjExOFx1YWNhOFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDI5XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWNjMjhcdWIyOTQgJDEkXHViOWFjXHVkMTMwXHVjNzU4IFx1YzVmMFx1YjhjY1x1Yjg1YyAkMSRcdWQwYWNcdWI4NWNcdWJiZjhcdWQxMzBcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzBjOCBcdWNjMjhcdWIyOTQgXHVjMmRjXHVjNmI0XHVjODA0IFx1YzgwNFx1YzVkMFx1YjI5NCBcdWM1ZjBcdWI4Y2NcdWFjMDAgXHVjNWM2XHVjMmI1XHViMmM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjYzI4XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM5YzBcdWM4MTBcdWM3NDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOVx1YzgwMVx1YzljMFx1YjI5NCBcdWFlMzhcdWM3NTggXHVjNmQwXHVjODEwXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyAkWCRcdWQwYWNcdWI4NWNcdWJiZjhcdWQxMzAgXHViNWE4XHVjNWI0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NDBcdWQ1NThcdWIyOTQgXHVjNWY0XHVjMmVjXHVkNzg4IFx1YmM4OCBcdWIzYzhcdWM3NDQgXHVjNWYwXHViOGNjXHVjNWQwIFx1YzRmMFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHVhZTRjXHVjNmNjLCBcdWJhYTlcdWM4MDFcdWM5YzBcdWFlNGNcdWM5YzAgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjQgXHVkNTY5XHViMmM4XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHVjNzQwXHVkNTU4XHViOTdjIFx1YjNjNFx1YzY0MCBcdWM4ZmNcdWM1YjRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM3MjBcdWMxOGNcdWM3NTggXHVhYzFjXHVjMjE4ICROJCwgXHViYWE5XHVkNDVjIFx1YzljMFx1YzgxMCAkWCQgXHViYzBmIFx1Y2MyOFx1Yzc1OCBcdWM1ZjBcdWI4Y2MgXHVjNmE5XHViN2M5ICRGJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMVxcbGVxIE5cXGxlcSA1MDBcXCwgMDAwOyQgJDFcXGxlcSBYLEZcXGxlcSAxMF57OX0pJDxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzhmY1x1YzcyMFx1YzE4Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWJhYThcdWI0ZTAgJDFcXGxlcSBpXFxsZXEgTiRcdWM1ZDAgXHViMzAwXHVkNTc0LCAkKGkrMSkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkeF97aX0kLCAkcF97aX0kLCAkYV97aX0kXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgwXFxsZXEgeF97aX0mbHQ7WCQ7ICQxXFxsZXEgcF97aX1cXGxlcSAxMF57OX0kOyAkMVxcbGVxIGFfe2l9XFxsZXEgRikkIFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzhmY1x1YzcyMFx1YzE4Y1x1YjI5NCBcdWM1YzZcdWM3M2NcdWJhNzAsIDxzdHJvbmc+XHVjOGZjXHVjNzIwXHVjMThjXHVjNzU4IFx1YzcwNFx1Y2U1OCAkeF97aX0kXHViMjk0IFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvc3Ryb25nPiBcdWM5ODksIFx1YmFhOFx1YjRlMCAkMlxcbGVxIGlcXGxlcSBOJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJHhfe2ktMX0mbHQ7eF97aX0kXHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzViNFx1YjVhNCBcdWFjYmRcdWI4NWNcdWI4NWMgXHVjMmRjXHVjNmI0XHVjODA0XHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU3NFx1YjNjNCBcdWJhYTlcdWM4MDFcdWM5YzBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJhNzQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+LTE8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1YzZiNFx1YzgwNFx1Yzc0NCBcdWI5YzhcdWNlNThcdWIyOTQgXHViMzcwIFx1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTM5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhcyBTdGF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5FdW5oYSBoYXMgbWFuYWdlZCB0byBidXkgYSBuZXcgY2FyIGFzIGEgcmVzdWx0IG9mIGhlciBoYXJkIHdvcmshIEZvciBoZXIgdGVzdCBkcml2ZSwgc2hlIHBsYW5zIHRvIGRyaXZlIGFsb25nIGEgc3RyYWlnaHQgcm9hZCB0b3dhcmRzIGhlciBkZXN0aW5hdGlvbi4gU2luY2UgaXQmIzM5O3MgYSBsb25nIGRyaXZlLCBzaGUgaXMgZ29pbmcgdG8gc3RvcCBhdCBzb21lIGdhcyBzdGF0aW9ucyBvbiB0aGUgd2F5IHRvIHJlZnVlbC4gVGhlIGZvbGxvd2luZyBjb25kaXRpb25zIG11c3QgYmUgc2F0aXNmaWVkIHRocm91Z2ggdGhlIHRlc3QgZHJpdmUuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlICRpJC10aCBnYXMgc3RhdGlvbiBpcyAkeF97aX0kIGtpbG9tZXRlcnMgYXdheSB0byB0aGUgcmlnaHQgZnJvbSB0aGUgb3JpZ2luLiBSZWZ1ZWxpbmcgYXQgdGhpcyBzdGF0aW9uIGNvc3RzICRwX3tpfSQgcGVyIGxpdGVyIG9mIGZ1ZWwsIGFuZCB0aGVyZSBpcyBhIHRvdGFsIG9mICRhX3tpfSQgbGl0ZXJzIG9mIGZ1ZWwgYXQgdGhlIHN0YXRpb24uPFwvbGk+XHJcblx0PGxpPllvdSBtYXkgcmVmdWVsIGFzIG11Y2ggYXMgeW91IHdhbnQgYXQgYSBnYXMgc3RhdGlvbiB1cCB0byAkYV97aX0kIGxpdGVycy48XC9saT5cclxuXHQ8bGk+VGhlIHRvdGFsIGFtb3VudCBvZiBmdWVsIGluIHRoZSBjYXIgYWZ0ZXIgcmVmdWVsaW5nIG11c3Qgbm90IGV4Y2VlZCB0aGUgY2FyJiMzOTtzIGNhcGFjaXR5ICRGJC48XC9saT5cclxuXHQ8bGk+VGhlIGNhciBjYW4gdHJhdmVsICQxJCBraWxvbWV0ZXIgdXNpbmcgJDEkIGxpdGVyIG9mIGZ1ZWwuPFwvbGk+XHJcblx0PGxpPlRoZSBjYXIgaGFzIG5vIGZ1ZWwgYXQgdGhlIHN0YXJ0IG9mIHRoZSB0ZXN0IGRyaXZlLiBUaHVzLCB0aGUgc3RhcnRpbmcgcG9pbnQgb2YgdGhlIGRyaXZlIGlzIHRoZSBmaXJzdCBnYXMgc3RhdGlvbi48XC9saT5cclxuXHQ8bGk+VGhlIGRlc3RpbmF0aW9uIGlzICRYJCBraWxvbWV0ZXJzIGF3YXkgdG8gdGhlIHJpZ2h0IGZyb20gdGhlIG9yaWdpbiBvZiB0aGUgcm9hZC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5FdW5oYSBmaW5kcyBpdCBhIHdhc3RlIHRvIHNwZW5kIGhlciBwcmVjaW91cyBtb25leSBvbiBmdWVsIGFuZCB0aHVzIHdpc2hlcyB0byB0cmF2ZWwgdG8gaGVyIGRlc3RpbmF0aW9uIHdpdGggbWluaW11bSBjb3N0LiBJdCYjMzk7cyB5b3VyIHRhc2sgdG8gaGVscCBFdW5oYSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkTiQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgZ2FzIHN0YXRpb25zLCAkWCQsIGRlbm90aW5nIHRoZSBkZXN0aW5hdGlvbiBwb2ludCwgYW5kICRGJCwgZGVub3RpbmcgdGhlIGNhciYjMzk7cyBmdWVsIGNhcGFjaXR5LiAkKDFcXGxlcSBOXFxsZXEgNTAwXFwsIDAwMDskICQxXFxsZXEgWCxGXFxsZXEgMTBeezl9KSQ8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCAkTiQgbGluZXMgb2YgaW5wdXQgY29udGFpbnMgaW5mb3JtYXRpb24gYWJvdXQgYSBnYXMgc3RhdGlvbi4gRm9yIGFsbCAkaSQgc3VjaCB0aGF0ICQxXFxsZXEgaVxcbGVxIE4kLCB0aGUgJChpKzEpJC10aCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICR4X3tpfSQsICRwX3tpfSQsIGFuZCAkYV97aX0kIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMFxcbGVxIHhfe2l9Jmx0O1gkOyAkMVxcbGVxIHBfe2l9XFxsZXEgMTBeezl9JDsgJDFcXGxlcSBhX3tpfVxcbGVxIEYpJCBObyB0d28gZ2FzIHN0YXRpb25zIGFyZSBhdCB0aGUgc2FtZSBsb2NhdGlvbiwgYW5kIHRoZSA8c3Ryb25nPmxvY2F0aW9ucyBhcmUgZ2l2ZW4gaW4gYXNjZW5kaW5nIG9yZGVyIG9mICR4X3tpfSQuIDxcL3N0cm9uZz5UaGF0IGlzLCBmb3IgYWxsICQyXFxsZXEgaVxcbGVxIE4kLCAkeF97aS0xfSZsdDt4X3tpfSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlcmUgaXMgbm8gcm91dGUgdGhhdCBhbGxvd3MgRXVuaGEgdG8gYXJyaXZlIGF0IGhlciBkZXN0aW5hdGlvbiwgcHJpbnQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPi0xPFwvY29kZT48XC9zcGFuPiZuYnNwO2luIHRoZSBmaXJzdCBsaW5lLiBPdGhlcndpc2UsIHByaW50IHRoZSBtaW5pbXVtIGNvc3QgcmVxdWlyZWQgdG8gY29tcGxldGUgdGhlIHRlc3QgZHJpdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==