Let's generate the weighted directed graph of all ramps. The graphs' vertexes are the important points on the line Ox, there are points: 0, L, xi - pi, xi + di. The graphs' edges are the possible ramp jumps: transfer from point xi - pi to point xi + di or transfer from vertex in neighboring vertexes (neighboring means that we get the next and previous important points on the line). The weights of these edges are correspondingly pi + ti and xv + 1 - xv, xv - xv - 1. We must note that in the transfers we can't get in the negative part of Ox, and we must delete this transfers.
Then we must find and output the shortest path in this graph from vertex 0 to L. This can be done, for example, with Dijkstra's algorithm for the sparse graphs.
In this problem we must find the minimum spanning tree, in which the half of edges are marked with letter 'S'.
There are n - 1 edges in this tree, because of it if n is even then the answer is "-1".
Let's delete from the given graph all S-edges. And there are cnt components in obtained graph. For making this graph be connected we must add cnt - 1 edges or more, that's why if cnt - 1 > (n - 1) / 2 the answer is "-1". Then we find cnt - 1 S-edges, that we must add to the graph, so that it become connected. If cnt - 1 < (n - 1) / 2 then we will try to add in this set of edges another S-edges, so that the S-edges don't make circle. We must do all of this analogically to Kruskal's algorithm of finding a minimum spanning tree. If we could get a set of S-edges of (n - 1) / 2 elements, that there are exactly cnt - 1 edges and no S-circles, then the answer exists, Then we must add to this set (n - 1) / 2 M-edges, that forms with our set of edges the minimum spanning tree, it must be done analogically with Kruskal's algorithm.