Minimum Red Length Sum

You are given n segments. The i‑th segment is given by the closed interval \( [l_i,r_i] \). You have to color each segment either red or black subject to the following conditions:

• Any two red segments do not intersect.
• Every black segment intersects with at least one red segment.

The length of a segment \( [l_i,r_i] \) is defined as \( r_i - l_i \). Two segments \( [l_i,r_i] \) and \( [l_j,r_j] \) are said to intersect if and only if there exists a point \( k \) such that \( k\in[l_i,r_i] \) and \( k\in[l_j,r_j] \).

Your task is to choose some segments to be red fulfilling the above conditions so that the sum of the lengths of all red segments is minimized. Output that minimum sum.

Note: The red segments you choose must be pairwise non-intersecting, and every segment that is colored black must intersect with at least one red segment.

inputFormat

The first line contains a single integer \( n \) indicating the number of segments.

Each of the next \( n \) lines contains two integers \( l_i \) and \( r_i \) which describe the endpoints of the segment \( [l_i, r_i] \).

outputFormat

Output a single integer which is the minimum possible sum of the lengths of the red segments that satisfy the conditions.

sample

3
1 3
2 4
3 5

2