#6557. 霸王龙的进化之路

霸王龙的进化之路

题目背景

霸王龙为了能够早日进化成宇宙超级无敌霸王龙神,他需要积累尽量多的声望。

题目描述

现在有 nn 项试炼。每完成一项试炼,都需要花费霸王龙完整的 11 天时间,且它同一时间只能专注完成一项试炼,无法同时进行多个任务。

每项试炼都有两个核心属性:

  1. 最晚完成期限 dd:这项试炼必须在第 dd 天结束前完成,一旦超过期限,试炼就会被取消,无法获得对应奖励。举例:某个试炼的最晚完成日期是3的话,那么霸王龙在第1、2、3天完成这个任务都是可以的。
  2. 声望值 vv:如果能按时完成这项试炼,霸王龙就能获得对应的族群声望。

霸王龙想尽可能多地积累声望,却不知道该怎么安排每天的试炼计划,请你帮它规划最优日程,算出它最多能获得多少总声望。

输入格式

第一行一个正整数 nn,表示试炼任务的总数。
接下来 nn 行,每行两个正整数 d,vd, v,分别表示该试炼的最晚完成期限和完成可获得的声望值。

输出格式

一行一个整数,表示霸王龙所能获得的最大总声望值。

样例 #1

样例输入 #1

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

样例输出 #1

15

样例解释

一种最优安排是:第 11 天完成第 22 项试炼(声望 77),第 22 天完成第 66 项试炼(声望 55),第 33 天完成第 33 项试炼(声望 22),第 66 天完成第 77 项试炼(声望 11)。总声望为 7+5+2+1=157+5+2+1=15

数据范围与提示

对于全部数据:1n1041 \le n \le 10^41dn1 \le d \le n1v7×1051 \le v \le 7 \times 10^5

子任务 分值 nn \le 特殊约定
1 10 1010
2 20 20002000
3 15 10410^4 di=nd_i = n
4 vi=1v_i = 1
5 40