题目背景

注意到本题特殊的时间限制。

普通版。

题目描述

给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$，将他们染成红色或黑色，要求：

1. 任意两条红色不相交
2. 任意一条黑色至少和一条红色相交。

请最小化红色线段的长度和，并输出这个长度和。

一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交当且仅当存在 $k\in[l_i,r_i]$ 且 $k\in[l_j,r_j]$。

输入格式

第一行一行一个正整数，代表 $n$。

接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。

输出格式

一行一个非负整数，代表最小的红色线段的长度和。

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

4

提示

数据范围

对于所有数据，满足 $-10^9\le l_i<r_i\le10^9$。

本题采用捆绑测试。