UOJ Logo AYIT Online Judge

AYITOJ

#38. 猴子吃桃

统计
时间限制:2s    内存限制:256M    满分: 100分

题目描述

动物园里有一只猴子

每隔一段时间, 饲养员会发给猴子一定数量的桃子

猴子每天最多会吃一个桃子, 当然它也可以选择不吃, 而是吃其他东西

每颗桃子都有一个甜蜜度 $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分)

无其他限制

题目来源

zdw1999