第四题：区间选点最小成本
题目描述
给定 n 个闭区间 [Lᵢ, Rᵢ]。需在数轴上选择一个整数点的集合 P = {p₁, p₂, …, pₖ}，满足以下两个条件：
-
对于每一个给定的区间 [Lᵢ, Rᵢ]，都至少存在一个点 pⱼ ∈ P，使得 Lᵢ ≤ pⱼ ≤ Rᵢ。 -
定义选择 P 的方案的总成本为 Σpⱼ（即集合中所有点的和），需使总成本最小。
计算这个最小的总成本。
输入格式
-
第一行包含一个整数 n，表示区间的数量。 -
接下来 n 行，每行包含两个整数 Lᵢ 和 Rᵢ，描述一个区间的左右端点。
输出格式
输出一个整数，表示满足条件的最小总成本。
输入输出样例
|
|
|
|---|---|
|
1 5 3 7 6 8 |
|
样例解释
选择点 1 和 6，总成本为 1 + 6 = 7，可覆盖所有区间（1 覆盖 [1,5] 和 [3,7]，6 覆盖 [6,8]）。
数据范围
对于 100% 的数据，满足 1 ≤ n ≤ 10⁵，1 ≤ Lᵢ ≤ Rᵢ ≤ 10⁹。
