Minimize the Total Length of Red Segments

You are given (n) segments on the number line. The (i)th segment is ([l_i, r_i]). You have to color each segment either red or black under the following conditions:

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

A segment ([l_i, r_i]) has a length defined as (r_i - l_i). Two segments ([l_i, r_i]) and ([l_j, r_j]) intersect if and only if (l_i \le r_j) and (l_j \le r_i).

Find the minimum possible sum of lengths of the red segments such that all conditions are satisfied, and output that sum.

Note: The conditions enforce that the set of red segments forms an independent dominating set on the interval intersection graph of the segments. In other words, the chosen red segments do not intersect with each other, and every segment (red or black) intersects at least one red segment.

inputFormat

The first line contains a single integer (n) ( (1 \le n \le 10^5)), the number of segments. Each of the next (n) lines contains two integers (l_i) and (r_i) ( (l_i < r_i)) describing a segment.

outputFormat

Output a single integer, the minimum total length of the red segments required.

sample

3
1 3
2 5
4 6

3