Problem Description

Given $n$ line segments, where the $i$-th segment is $[l_i,r_i]$. Color each segment either red or black, with the following requirements:

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

Minimize the total length of the red segments, and output this total length.

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]$ intersect if and only if $l_i\le r_j$ and $l_j\le r_i$.

Input Format

The first line contains one positive integer $n$.

The next $n$ lines each contain two integers $l_i,r_i$, separated by a space.

Output Format

Output one non-negative integer, representing the minimum possible total length of the red segments.

5
-6 5
1 3
-4 9
-1 10
6 8

4

Hint

Constraints

For all testdata, $-10^9\le l_i<r_i\le10^9$.

Translated by ChatGPT 5