This problem can be considered as a shortest path problem.

Regarding each stage as a vertex and an action at each station as an edge, this problem essentially asks: there is a graph with \(N\) vertices numbered \(1,2,\ldots,N\), and with edges from vertex \(i\) to vertex \((i+1)\) of cost \(A_i\), and from vertex \(i\) to vertex \(X_i\) with cost \(B_i\). What is the minimum cost required to travel from vertex \(1\) to vertex \(N\)?

This is nothing but a shortest path problem, so one can solve it using Dijkstra’s algorithm in a total of \(O(N\log N)\) time.

Figure: the graph corresponding to sample input 1