题目描述

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

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

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

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

输入格式

第一行一行一个正整数，代表 $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$。