There are \(N\) upright poles placed in a row, numbered \(1, 2, \ldots, N\) from left to right. The \(i^{th}\) pole is affixed to a position \(D_i\) right of the origin, and extends from the ground to a height \(H_i\). In addition, pole \(1\) stands right on the origin, i.e. \(D_1 = 0\).
A flying squirrel rests at height \(L\) on pole \(1\). Now, the squirrel wants to go through all the poles from left to right, and ultimately reach a height \(R\) on pole \(N\).
To get between poles, the flying squirrel can glide from one adjacent pole to the next  the squirrel glides in perfect diagonals, dropping a distance \(d\) in height whenever it glides \(d\) units towards the right. The squirrel must not land on the ground between poles, but may reach a pole exactly at height \(0\).
The flying squirrel may also climb up or down each pole. On any pole \(i\), it takes \(W_i\) effort for the squirrel to climb \(1\) unit up the pole, and no effort for it to climb down. The squirrel cannot climb above its current pole's height \(H_i\), or into the ground.
Figure 1 below shows a valid path the squirrel may take.
The first line of input consists of a single integer \(N\), the number of poles in the arrangement.
\(N\) lines of input follow. The \(i^{th}\) of these lines contains 3 integers \(D_i\), \(H_i\), and \(W_i\), denoting that the \(i^{th}\) pole is located \(D_i\) from the left, has a height of \(H_i\), and requires \(W_i\) effort for the flying squirrel to ascend one unit on.
One line of input follows. This line contains 2 integers \(L_i\) and \(R_i\), the initial height of the squirrel on the \(1^{st}\) pole and its destination height on the \(N^{th}\) pole respectively.
Output a single integer on a single line  the minimum effort required for the squirrel to reach its destination through a valid path, or \(1\) if no such path exists.
Subtask #  Score  Constraints 

1  4  \(W_i = 0\) \((1 \leq i \leq N)\) 
2  13  \(W_i = 1\) \((1 \leq i \leq N)\) 
3  18  \(W_i \leq W_{i + 1}\) \((1 \leq i \leq N  1)\) 
4  15  \(N \leq 500\) \(H_i \leq 500\) \((1 \leq i \leq N)\) 
5  18  \(N \leq 5000\) 
6  32  No additional constraints 
Sample Input 1  Sample Output 1 
3

18

In this input example, it is optimal for the squirrel to climb 2 units up pole 1 to reach a height of 7, glide to the top of pole 2 and then to height 3 on pole 3, before climbing 2 units up pole 3 to reach its destination.
This takes a total effort of \(2 \cdot 3 + 2 \cdot 6 = 18\).
Subtask  Score 

1  4 
2  13 
3  18 
4  15 
5  18 
6  32 
7  0 