Background

Note the special time limit of this problem.

Normal Version.

Problem Description

Given $n$ line segments, where the $i$-th segment is $[l_i, r_i]$, color each segment either red or black, such that:

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 there exists $k \in [l_i, r_i]$ and $k \in [l_j, r_j]$.

Input Format

The first line contains a 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: 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 \le 10^9$.

This problem uses bundled tests.

Translated by ChatGPT 5