Problem F: Timing

Problem

$N$頂点$M$辺の無向グラフが与えられる。各頂点には相異なる$1$から$N$までの番号が定められている。あなたは時刻$0$に頂点$S$を出発し、頂点$G$まで移動したい。各辺にはパラメータ$a, b$が設定されていて、時刻$t$にその辺の片側の頂点から出発した場合、もう片側の頂点には時刻$t+ceil\left(\cfrac{b}{t+a}\right)$に到達することがわかっている。ここで、$ceil(x)$は$x$以上の最小の整数を表す。また、各頂点では任意の非負整数時間を余分に消費することができる。つまり、時刻$t$にある頂点にいるとき、任意の非負整数$k$を選び、時刻$t+k$になるまで待機することができる。最速最強アルゴリズマーを目指すあなたは、頂点$S$から頂点$G$まで移動するためにかかる時間の最小値を求めたくなった。

Input

入力は以下の形式で与えられる。

$N$ $M$ $S$ $G$
$U_1$ $V_1$ $A_1$ $B_1$
$U_2$ $V_2$ $A_2$ $B_2$
:
$U_M$ $V_M$ $A_M$ $B_M$

$1$行目に、与えられるグラフの頂点数$N$、辺数$M$、スタートの頂点番号$S$、ゴールの頂点番号$G$が空白区切りで与えられる。
続く$M$行に、各辺の情報が空白区切りで与えられる。$i$行目の情報は、頂点$U_i$と頂点$V_i$の間に$(a, b) = (A_i, B_i)$であるような辺が存在することを表す。

Constraints

入力は以下の条件を満たす。

• $1 \le N, M \le 2 \times 10^5$
• $1 \le S, G \le N$, $S \neq G$
• $1 \le U_i, V_i \le N$, $U_i \neq V_i (1 \le i \le M)$
• $1 \le A_i, B_i \le 10^{15} (1 \le i \le M)$
• 与えられる入力は全て整数である

Output

頂点$S$から頂点$G$まで移動するためにかかる時間の最小値を出力せよ。頂点$S$から頂点$G$に移動できない場合は、代わりに$-1$を出力せよ。

Sample Input 1

2 1 1 2
1 2 1 100

Sample Output 1

19

Sample Input 2

2 1 1 2
1 2 50 100

Sample Output 2

2  

Sample Input 3

3 1 1 3
1 2 1 1

Sample Output 3

-1

Sample Input 4

3 3 1 3
1 2 1 1
2 3 1 6
2 3 50 100

Sample Output 4

3

Sample Input 5

3 3 1 3
1 2 10 100
2 3 1 6
2 3 50 100

Sample Output 5

11