[ONTAK2015]Bajtman i Okrągły Robin

时间限制:40s      空间限制:256MB

题目描述

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


输入格式

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


输出格式

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


样例输入

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

样例输出

90

提示

没有写明提示


题目来源

By Claris

Menuappsclose