$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$まで移動するためにかかる時間の最小値を求めたくなった。
入力は以下の形式で与えられる。
$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)$であるような辺が存在することを表す。
入力は以下の条件を満たす。
頂点$S$から頂点$G$まで移動するためにかかる時間の最小値を出力せよ。頂点$S$から頂点$G$に移動できない場合は、代わりに$-1$を出力せよ。
2 1 1 2 1 2 1 100
19頂点$1$で時間を$9$消費し、時刻$9$に辺$1$を使うと、辺の所要時間は$ceil\left(\cfrac{100}{10}\right) = 10$となり、時刻$19$に頂点$2$に到達できる。これが最短である。
2 1 1 2 1 2 50 100
2時刻$0$に辺$1$を使うのが最適である。
3 1 1 3 1 2 1 1
-1頂点$S$から頂点$G$に移動できない場合もある。
3 3 1 3 1 2 1 1 2 3 1 6 2 3 50 100
3
3 3 1 3 1 2 10 100 2 3 1 6 2 3 50 100
11