この問題は最短経路問題とみなすことができます。

各ステージを頂点とし、各ステージでの行動を辺とすることで、「\(1,2,\ldots,N\) の \(N\) 個の頂点を持ち、頂点 \(i\) から頂点 \(i+1\) へ向かうコスト \(A_i\) の辺と、頂点 \(i\) から頂点 \(X_i\) へ向かうコスト \(B_i\) の辺があるとき、頂点 \(1\) から頂点 \(N\) へ移動するための最小コストは？」という問題になります。

これは最短経路問題そのものなので、ダイクストラ法を用いることで\(O(N\log N)\) 時間で答えを求めることができます。

図：入力例1に対応するグラフ