| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 10 | 6 | 5 | 55.556% |
Мало кто знает, почему магическая технология такая эффективная. На самом деле любой магический кристалл можно представить в виде $n$ узлов и $m$ двухсторонних связей между ними. Иногда в некоторых узлах вспыхивают искры энергии, которые затем распространяются в соседние узлы, из них --- в соседние с ними, и так далее.
Недавно исследователи академии Пилтовера во главе с Хеймердингером выяснили, что делает магические кристаллы особенно сильными. Некоторые из связей между узлами являются накопительными. Это означает, что энергия может проходить через них только в определенные периоды времени, а вне этих периодов скапливается в концах этих связей и сохраняется в них.
Для каждой связи известно, сколько времени уходит на перемещение энергии из одного ее конца в другой. Также, для всех накопительных связей известно, что они пропускают энергию в одни и те же интервалы времени. Эти интервалы задаются списком пар моментов времени $(x_i, y_i),ドル означающими, что между моментами времени $x_i$ и $y_i$ включительно каждая связь открыта и пропускает энергию. В остальные моменты времени они закрыты, и энергия <<задерживается>> в их концах.
Важно отметить, что если накопительная связь закрывается в тот момент, когда энергия перемещается по ней, энергия продолжает двигаться в ту сторону, в которую двигалась. Иными словами, если в момент $t$ связь длиной $w$ открыта, и в этот же момент $t$ к одному ее концу приходит искра энергии, то в момент $t + w$ она доберется до второго конца, даже если связь закроется к этому времени.
Для создания нового магического оружия необходимо определить, в какой момент времени энергия впервые дойдет до узла $v,ドル если искра зародится в узле $u$ в момент времени $t_0,ドル или что энергия не дойдет до узла $v$ вообще.
В первой строке ввода даны три целых числа $n,ドル $m,ドル $k$ --- количество узлов кристалла и связей между ними, а также количество пар моментов времени, между которыми все накопительные связи открыты (2ドル \leqslant n \leqslant 10^{5}$; 1ドル \leqslant m \leqslant 10^{6},ドル 1ドル \leqslant k \leqslant 10^{5}$).
В $i$-й из следующих $m$ строк через пробел даны четыре целых числа $a_i,ドル $b_i,ドル $w_i$ и $f_i$. Первые два числа $a_i$ и $b_i$ --- номера узлов, которые соединяет $i$-я связь (1ドル \leqslant a_i, b_i \leqslant n$; $a_i \neq b_i$). Число $w_i$ --- время, за которое энергия перемещается между концами связи (1ドル \leqslant w_i \leqslant 10^{9}$). Число $f_i$ задает, является ли $i$-я связь накопительной. Он равен 1ドル,ドル если является, и 0ドル$ иначе.
В каждой из следующих $k$ строк записаны по два целых числа $x_i,ドル $y_i$ --- моменты времени, между которыми (включительно) каждая накопительная связь открыта и может перемещать энергию (1ドル \leqslant x_i \leqslant y_i \leqslant 10^{18}$; $y_{i-1} < x_{i}$ для всех $i$).
В последней строке ввода даны три целых числа $u,ドル $v$ и $t_0$ --- номера стартового и конечного узла, а также время зарождения искры энергии в стартовом узле (1ドル \leqslant u, v \leqslant n$; 1ドル \leqslant t_0 \leqslant 10^{18}$).
Выведите одно целое число --- через какое минимальное время энергия впервые дойдет от узла $u$ до узла $v,ドル начав движение в момент времени $t_0$. Если она не дойдет до $v$ никогда, выведите <<-1>> (без кавычек).
2 1 1 1 2 1 0 2 3 1 2 3
1
6 8 2 1 2 1 0 3 5 5 0 3 4 1 1 2 4 2 0 3 6 3 1 4 6 1 0 5 6 1 1 1 6 1 1 6 6 39 40 2 5 8
32