천재적인 산책

Sam은 새로운 지역에서 도시 $n$개를 발견했다. 이 도시들은 양방향 도로 $m$개로 연결되어 있다. Sam은 도로를 따라서만 이동할 수 있다. Sam은 시간적 비를 맞지 않고 도시 $s$에서 도시 $t$로 가야 한다. 일기 예보에 따르면 $i$번째 도로에는 모든 정수 $k$에 대해 구간 $[(a_i + b_i) \cdot k + a_i, (a_i + b_i) \cdot (k + 1)]$ 동안 비가 내린다 ($a_i$와 $b_i$는 양수이다). Sam이 $i$번째 도로를 지나려면 $d_i$의 시간이 걸리고, 이 시간 내내 그 도로에 비가 내리면 안 된다. 도시에서는 비를 피할 수 있으므로 Sam은 언제든 도시에 머물 수 있다. Sam은 비가 그치는 순간에 도시에서 도로로 나갈 수 있고, 비가 시작되는 순간에 도로에서 도시로 들어올 수 있다.

시각 0에 Sam은 도시 $s$에 있다. Sam이 도시 $t$에 있을 수 있는 가장 이른 시각을 구하라.

첫 줄에 정수 네 개 $n$, $m$, $s$, $t$가 주어진다. 각각 도시의 수, 도로의 수, 출발 도시, 도착 도시이다 ($1 \le n \le 100000$; $0 \le m \le 200000$; $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$를 잇는다.

Sam이 도시 $s$에서 도시 $t$로 갈 수 없으면 $-1$을 출력한다. 그렇지 않으면 Sam이 도시 $t$에 있을 수 있는 가장 이른 시각을 출력한다.