В новом регионе Сэм обнаружил $$$n$$$ городов, соединенных $$$m$$$ двусторонними дорогами. Сэм может перемещаться только по дорогам. Ему нужно добраться из города $$$s$$$ в город $$$t$$$, и при этом не попасть под темпоральный дождь. Согласно прогнозу погоды, дождь над $$$i$$$-й дорогой будет идти в отрезки времени $$$[(a_i + b_i) \cdot k + a_i, (a_i + b_i) \cdot (k + 1)]$$$ для всех целых $$$k$$$ ($$$a_i$$$ и $$$b_i$$$ — положительны). Чтобы пройти по $$$i$$$-й дороге, Сэм должен потратить $$$d_i$$$ времени, и на протяжении всего этого времени над этой дорогой не должен идти дождь. В городах Сэм может укрыться от дождя, поэтому в них он может находиться в любое время. Также, Сэм может выйти из города на дорогу в момент окончания дождя и зайти в город с дороги в момент начала дождя.
В момент времени $$$0$$$, Сэм находится в городе $$$s$$$, и интересуется, в какой минимальный момент времени он может оказаться в городе $$$t$$$. Помогите ему ответить на этот вопрос.
В первой строке даны четыре целых числа $$$n$$$, $$$m$$$, $$$s$$$ и $$$t$$$ — количество городов, дорог, стартовый и конечный город соответственно ($$$1 \le n \le 100\,000$$$; $$$0 \le m \le 200\,000$$$; $$$1 \le s, t \le n$$$). В следующих $$$m$$$ строках дано описание дорог. В каждой строке дано пять целых чисел $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, $$$b_i$$$ и $$$d_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$1 \le a_i, b_i, d_i \le 10^9$$$). Дорога номер $$$i$$$ соединяет города $$$u_i$$$ и $$$v_i$$$.
Если Сэм не может добраться из города $$$s$$$ до города $$$t$$$, выведите «-1», иначе выведите минимальный момент времени, в который он может оказаться в городе $$$t$$$.
3 2 1 3 1 2 3 4 1 2 3 2 3 2
7