3-10 反抗内卷
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
反抗内卷
时间限制:1s
空间限制:256MB
Description
本学期,小L参加了学院开设的《算法设计与分析》课程,选课的学生共有n个。在期末考试前,每个人都需要提交一篇论文《论算法设计的艺术》。记\(w_i\)为第i位学生的论文字数。
由于能力不同,每位学生的论文字数都有一个下界\(L_i\)和一个上界\(R_i\),即\(L_i ≤ w_i ≤R_i\)。
恶贯满盈的任课教师季老师定下了一个打分规则——对于某个学生而言,若在所有n个学生中,有k个学生的论文字数大于他的论文字数,则他的论文分数是n-k。在这样的规则下,每个同学都想尽力多写来获取高分。最终,每个同学都决定写\(R_i\)个字。
为了反抗内卷,小L把大家召集起来,希望大家一起减少论文字数。
经过协商,同学们统一决定让小L决定每个同学写多少字,但是有以下两点要求:
1.在新方案下,每个同学的成绩不能比原来低。
2.小L希望在要求1的基础上,每个同学的论文字数之和最小。
小L不知道该怎么设计方案,于是他找到了会编程的你,希望你能够给出每个同学\(w_i\)之和的最小值。
Input Format
第一行包含单个整数 \(n(1 \leq n \leq 10^5)\) ,即学生的总数。
以下 \(n\) 行中的每一行都有两个以空格分隔的整数 \(L_i\) 和 \(R_i\) \((1 ≤ L_i ≤ R_i≤10^9)\)
Output Format
输出一个整数,表示每个同学\(w_i\)之和的最小值
Data Range
- \(1 \leq n \leq 10^5\)
- \(1 ≤ L_i ≤ R_i≤10^9\)
Input Example #1:
3
1 10000
1 10000
1 10000
Output Example #1:
3
Input Example #2:
4
1 2
2 2
2 4
3 4
Output Example #2:
10