#18123. 家庭作业

家庭作业

题目背景

众所周知,小 T 的老师是一个古怪的老师。

题目描述

小 T 老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 10 ,要求在 6 天内交,那么要想拿到这 10 学分,就必须在第 6 天结束前交。

小T每完成一项作业,都需要一天时间,现有 nn 项作业,给出你每项作业的最大期限和学分,小 T 想获得最多的学分,但不知道怎么安排时间,于是请聪明的你来帮忙。

输入格式

输入共 n+1n+1 行:

第一行一个正整数 nn (n1e6)( n≤1e6 )

22 行到第 n+1n+1 行,每行两个正整数,ttww,表示每项作业的最大期限和学分w7105( w≤7*105 )

输出格式

仅一行,表示小 T 所能获得最大的学分

输入输出样例 #1

输入 #1

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

输出 #1

15

说明/提示

样例的其中一种解法是: 26317542,6,3,1,7,5,4