Problem: Superphone

Want to try solving this problem? You can submit your code online if you log in or register.

Superphone

Input File: phonein.txt
Output File: phoneout.txt
Time Limit: 2 seconds

It is almost time. After months of waiting and media hype, the new all-in-one mobile phone, music player and electric toothbrush is about to be released. You have been waiting outside the tall store for the last twelve hours hoping to be the first to get your hands on one of these new phones. In just a few minutes, the store is going to open.

Unfortunately, a large number of other people have also been milling about outside the store, they too wanting to be the first to purchase one of these new phones. To ensure that they don't beat you to it, you will not only have to sprint to the sales desk of the store, but you will need to ensure that you take the absolute fastest route to get there.

The store is a large building consisting of several floors. Each floor has a pair of escalators that connect to the floor above, as shown in the figure below. The left-hand side of the building has an escalator to the right-hand side of the floor above, and the right-hand side of the building has an escalator to the left-hand side of the floor above. All of these escalators move up. Also, on each floor you are able to (if you wish) sprint to the other side of the building to get to the escalator on the other side.

The doors of the store, where you are currently waiting, are located to the left of bottom floor. The sales desk, where you must purchase your phone, is located on the right of the top floor.

$\includegraphics[scale=0.6]{escalator.eps}$

From your research, you know that different escalators move at different speeds, and some floors are more difficult to run through than others. Fortunately, you have carefully recorded precisely how many seconds it takes you to run up each individual escalator, as well as how many seconds it takes you to run from one side of each individual floor to the other.

Your task is to determine the minimum amount of time required to reach the sales desk of the building from the doors of the building.

Input

The first line of input will contain the single integer n representing the number of floors in the building, which includes both the ground floor and top floor of the building ( 2 <= n <= 100000).

The next (n-1) lines each correspond to a floor of the building, from the ground floor upwards. Each line will each contain three integers l f r separated by single spaces, where l represents the number of seconds required to travel from the left-hand side of the current floor to the right-hand side of the floor above, f the number of seconds to run from one side of the floor to the other, and r the number of seconds to travel from the right-hand side of the floor to the left-hand side of the floor above ( 1 <= l, f, r <= 1000).

The final line of input will contain a single integer f, the time in seconds required to run from one side of the top floor to the other side ( 1 <= f <= 1000).

Output

Your output file should consist of a single integer giving the smallest possible time in seconds required to reach the sales desk from your starting location.

Sample Input

Sample Output

Explanation

The sample input corresponds to the figure below.

$\includegraphics[scale=0.6]{escalatordist.eps}$

The optimal path is achieved as follows:

You take the escalator from the left side of the ground floor to the right side of the first floor (14 seconds);
You sprint across the first floor from the right side to the left (5 seconds);
You take the escalator from the left side of the first floor to the right side of the second floor (13 seconds);
You take the escalator from the right side of the second floor to the left side of the top floor (11 seconds);
You run from the left side to the right side of the top floor (5 seconds) to claim your phone!

The total time from the front doors to the sales desk is 14+5+13+11+5=48 seconds.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.