题目描述

有 n 个活动，每个活动有开始时间 s_i、结束时间 e_i 和价值 v_i。选择若干个互不重叠的活动，使得总价值最大。两个活动不重叠当且仅当一个活动的结束时间不超过另一个活动的开始时间。

输入格式

第一行一个整数 n (1 <= n <= 100)。 接下来 n 行，每行三个整数 s_i, e_i, v_i (0 <= s_i < e_i <= 10^9, 1 <= v_i <= 10^9)，分别表示第 i 个活动的开始时间、结束时间和价值。

输出格式

输出一个整数，表示可以选择的最大总价值。

样例

输入：

3
1 3 5
2 4 6
3 5 7

输出：

12

数据范围

• 1 <= n <= 100
• 0 <= s_i < e_i <= 10^9
• 1 <= v_i <= 10^9
• 答案可能超过 32 位整数，请使用 64 位整数。