006 - トランポリン

問題文

1 列に N 個のトランポリンが距離 1 の等間隔で並んでいます。 トランポリンには左端から 1 から N の番号が順に振られています。

トランポリン i(1 ≤ i ≤ N) の弾性力が A_i であることが分かっています。 トランポリン i を使用して, トランポリン i からの距離が A_i 以下のトランポリンに飛び移ることができます。 ただし, トランポリンがない場所には飛び移ることは出来ません。 トランポリン i を使用すると脚へのダメージ B_i を得ます。

うさぎちゃんはトランポリンを使って, トランポリン S から T に移動します。 トランポリン T は着地専用なので, 弾性力 A_T, 脚へのダメージ B_T ともに 0 であることが保証されています。 このとき, 脚へのダメージの和の最小値を求めてください。

入力

N S T
A1 B1
A2 B2
:
AN BN

1 行目にトランポリンの個数 N(2 ≤ N ≤ 200 000), 移動元のトランポリン S(1 ≤ S ≤ N), 移動先のトランポリン T (1 ≤ T ≤ N) が与えられます。 S ≠ T が保証されます。

つづく N 行にかけてトランポリンの情報が与えられます。 このうち i 行目は トランポリン i の弾性力が A_i(0 ≤ A_i ≤ 10⁹), 脚へのダメージが B_i(0 ≤ B_i ≤ 10⁹) であることを意味します。 A_T = 0, B_T = 0 が保証されます。

答えが 32bit 整数型に収まらないことがあるので注意してください。

部分点

採点データのうちの 1/3 はすべてのトランポリンについて A_i ≤ 1 を追加で満たします。

出力

1 行に, トランポリン S から T に移動するときにかかる脚へのダメージの和の最小値を出力してください。
どのようにトランポリンを使用しても S から T に到達できないとき, -1 を出力してください。
最後に改行してください。

入出力例

入力例 1

3 1 3
1 3
1 5
0 0

出力例 1

8

トランポリンを 1 -> 2 -> 3 の順で使う経路が最適です。 よって答えは 8 となります。

入力例 2

5 2 4
10 1
1 1
10 10
0 0
1 1

出力例 2

2

トランポリンを 2 -> 1 -> 4 の順で使う経路が最適です。 よって答えは 2 となります。

入力例 3

3 2 1
0 0
0 11
33 4

出力例 3

-1

A₂ = 0 なのでトランポリン 2 から他のトランポリンに移動することができません。 -1 を出力します。