P8592 『JROI-8』颅脑损伤 2.0（加强版）

注意到本题特殊的时间限制。 [普通版](https://www.luogu.com.cn/problem/P8591)。

给定 $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$，用空格隔开。

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

**数据范围** |测试点编号|$n\le$| | :----------: | :----------: | |$1\sim10$|$5\times 10^5$| 对于所有数据，满足 $-10^9\le l_i