环鸽的红包
题号：NC206544
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

盼着盼着，新年终于来了！今年春节，环鸽要去赚大钱！他要抢很多很多的红包！

设抢红包时间一共有 秒，第 个红包环鸽可以在第 秒收集，里面有 元。如果环鸽抢了这个红包，那么他在第 秒之后才能继续抢红包（不包括 ）。满足 。

环鸽不愿意多动脑子，于是他贪心地抢红包：如果第 秒的红包可以收集，他就会选择钱数最多的那个红包。如果有多个这样的红包，他就选择 最大的那个。

你突然得到了一个消息——环鸽没有抢到的红包，将全部归你！于是你决定去干扰环鸽抢红包。如果你在第 秒对环鸽喊 "嘤嘤嘤"，环鸽就无法在这一秒抢红包。在下一秒，环鸽将继续贪心地抢红包。你最多可以对环鸽喊 次 “嘤嘤嘤”。

输入描述:

第一行三个整数 

接下来  行代表  个红包，每行三个整数分别代表

输出描述:

输出一个整数代表你采用最优策略后能拿到的钱数。
示例1

输入

复制 
10 1 6
1 2 4
2 6 2
3 3 3
4 4 5
5 5 7
6 6 9

输出

复制 
28

说明

样例中，在第 \ 1 秒干扰环鸽。于是环鸽在第二秒抢到第 \ 2 个红包，然后他不能抢任何一个红包了。