题目描述
动物园里有一只猴子
每隔一段时间, 饲养员会发给猴子一定数量的桃子
猴子每天最多会吃一个桃子, 当然它也可以选择不吃, 而是吃其他东西
每颗桃子都有一个甜蜜度 $v_i$ , 而每过一天甜蜜度都会下降 $1$
给出饲养员给予猴子的桃子记录, 问猴子吃到的桃子的甜蜜度总和的最大值是多少?
请注意桃子是在一天结束时送来的, 也就是说猴子不能吃当天送来的桃子
输入描述
第一行一个整数 $n$ 表示饲养员给猴子发桃子的次数
接下来 $n$ 行每行3个整数 $a_i ,b_i ,c_i$ 表示猴子在第 $a_i$ 天收到了甜蜜度为 $b_i$ 的桃子 $c_i$ 个
输出描述
仅一行, 一个整数, 表示猴子吃到的桃子甜蜜度总和的最大值
具体见样例
样例输入
2 0 5 4 2 4 1
样例输出
11
样例描述
第 $0$ 天猴子没有桃子可吃, 这天结束时猴子收到了 $4$ 颗甜蜜度为 $5$ 的桃子.
第 $1$ 天猴子拥有 $4$ 颗桃子, 甜蜜度为 {$4,4,4,4$}, 于是它吃掉了 $1$ 颗甜蜜度为 $4$的桃子
(请注意虽然送来时桃子甜蜜度为 $5$ , 但桃子是昨天送来的所以甜蜜度已经 -1 了)
第 $2$ 天猴子拥有 $3$ 颗桃子, 甜蜜度为 {$3,3,3$}, 于是它吃掉了 $1$ 颗甜蜜度为 $3$的桃子
这天结束时猴子收到了 $1$ 颗甜蜜度为 $4$ 的桃子.
第 $3$ 天猴子拥有 $3$ 颗桃子, 甜蜜度为 {$3,2,2$}, 于是它吃掉了 $1$ 颗甜蜜度为 $2$的桃子
第 $4$ 天猴子拥有 $2$ 颗桃子, 甜蜜度为 {$2,1$}, 于是它吃掉了 $1$ 颗甜蜜度为 $1$的桃子
第 $5$ 天猴子拥有 $1$ 颗桃子, 甜蜜度为 {$1$}, 于是它吃掉了 $1$ 颗甜蜜度为 $1$的桃子
第 $6$ 天猴子吃光了所有的桃子, 且饲养员不会再送新桃子来了
猴子吃掉的桃子的总甜蜜度为: $4+3+2+1+1=11$
当然,得到这个结果的方案是不唯一的, 不过我们此处只要求结果
数据范围
$n <= 2*10^5$
$0 <= a_i,b_i,c_i <= 10^9$
$a_i < a_{i+1}$
子任务1:(10分)
$c_i$ = $1$
子任务2:(30分)
$a_i$ <= $2*10^5$
子任务3:(60分)
无其他限制
