最大总价值

题目描述

给定 n 个活动，每个活动有一个开始时间 s、结束时间 t 和价值 v。你需要选择一些活动，使得任意两个被选中的活动时间不重叠（即后一个活动的开始时间大于等于前一个活动的结束时间），并且使得所有被选中活动的总价值最大。求这个最大总价值。

输入格式

第一行一个整数 n (1 ≤ n ≤ 100)。 接下来 n 行，每行三个整数 s, t, v (1 ≤ s < t ≤ 10^6, 1 ≤ v ≤ 10^4)，表示一个活动的开始时间、结束时间和价值。

输出格式

输出一个整数，表示最大总价值。

样例输入

3 1 3 5 2 4 6 3 5 7

样例输出

12

数据范围

• 1 ≤ n ≤ 100
• 1 ≤ s < t ≤ 10^6
• 1 ≤ v ≤ 10^4
• 答案不超过 10^6，但建议使用 long long 存储。