006 - トランポリン

時間制限 1 秒 / メモリ制限 256 MB / 得点 300 / x 0 /


TLE
1sec
MLE
256MB
得点
300

問題文

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

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

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

入力

N S T
A1 B1
A2 B2
:
AN BN

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

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

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

部分点

採点データのうちの 1/3 はすべてのトランポリンについて Ai ≤ 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

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