UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4276. [ONTAK2015]Bajtman i Okrągły Robin

统计 下载数据

Description

有n个强盗,其中第i个强盗会在[a[i],a[i]+1],[a[i]+1,a[i]+2],...,[b[i]-1,b[i]]这么多段长度为1时间中选出一个时间进行抢劫,并计划抢走c[i]元。作为保安,你在每一段长度为1的时间内最多只能制止一个强盗,那么你最多可以挽回多少损失呢?

Input

第一行包含一个正整数n(1<=n<=5000),表示强盗的个数。
接下来n行,每行包含三个正整数a[i],b[i],c[i](1<=a[i]<b[i]<=5000,1<=c[i]<=10000),依次描述每一个强盗。

Output

输出一个整数,即可以挽回的损失的最大值。

Sample Input

4
1 4 40
2 4 10
2 3 30
1 3 20

Sample Output

90

Hint

Source

By Claris