Minimum Path Traversal on a Grid of Line Segments

You are given an integer n and an n × n grid. In each row i (1-indexed) there is a horizontal line segment with left endpoint at \( (i, L_i) \) and right endpoint at \( (i, R_i) \). You start at \( (1,1) \) and you must eventually reach \( (n,n) \). Your path must cover every line segment in each row; that is, before moving down from row i to row i+1, you must have visited every point on the segment in row i.

You are only allowed three types of moves:

• Move one step to the right (increase column by 1).
• Move one step to the left (decrease column by 1).
• Move one step down (increase row by 1).

Find the minimum number of steps required to go from \( (1,1) \) to \( (n,n) \) while satisfying the above conditions.

Note: When moving from one row to the next, you must have completely covered (visited) the line segment in the current row. To cover a segment in a row, you must travel in such a way that every point on that horizontal segment is passed. The optimal strategy for a row with segment \( [L_i, R_i] \) starting from a column \( x \) is determined by one of the two patterns:

To finish at the left endpoint \(L_i\): \[ \min\Bigl\{ |x - R_i| + (R_i - L_i), \; |x - L_i| + 2(R_i - L_i) \Bigr\} \]

To finish at the right endpoint \(R_i\): \[ \min\Bigl\{ |x - L_i| + (R_i - L_i), \; |x - R_i| + 2(R_i - L_i) \Bigr\} \]

Finally, after processing the last row, you must move horizontally to column \(n\) (if needed) to reach \( (n,n) \). The overall answer is the minimum total steps required.

inputFormat

The first line contains a single integer n (the number of rows).

Each of the next n lines contains two integers L_i and R_i, representing the left and right endpoints of the line segment in row i.

You may assume that all given numbers are positive integers.

outputFormat

Output a single integer, the minimum number of steps required to travel from (1,1) to (n,n) while covering all line segments as described.

sample

1
1 1

0