令你感到非常沮丧的是，你家里只有一台电视机。决定在任何给定时间观看什么电视节目是争吵的根源。例如，你的小妹妹安妮总是想看《绝望主妇》，而你却想看《犯罪现场调查》。你认为使用自动化工具来解决这些争论会很有帮助。

因此，你决定构建一个系统，来决定在任何给定时间应该播放哪个节目。在一个播出季中，每个节目通常每周都在完全相同的时间播出。因此，你决定针对一周的时间来解决这个问题，并让这个方案决定整个播出季的安排。家庭中的每个成员都被分配了 $y$ 点积分，他/她可以将这些积分分配给他/她最喜欢的节目。我们假设每个节目都在同一时间开始，并且每周持续 $d$ 分钟。每个电视节目随后会被分配到所有家庭成员给予它的积分总和。你应该编写一个程序，使你的电视机上播放的电视节目的总积分最大化。

输入格式

第一行输入给出一个整数 $1 \le t \le 30$，表示测试用例的数量。每个测试用例的第一行给出一个整数 $1 \le n \le 100000$，表示你的家庭给予了积分的电视节目数量。接下来有 $n$ 行，每行包含 3 个以空格分隔的整数 $s_i$、$d_i$ 和 $p_i$，其中每一行描述一个电视节目。$s_i$ 描述了节目 $i$ 开始的分钟数，$d_i$ 描述了节目 $i$ 持续的分钟数 ($0 \le s_i < s_i + d_i \le 10080$)。如果 $s_i + d_i = k$，这意味着你可以在时间 $k$ 开始观看一个新的节目。$p_i$ 描述了节目 $i$ 在你家中获得的积分总数 ($1 \le p_i \le 2000$)。

输出格式

对于每个测试用例，输出一行，包含电视机上播放的电视节目的最大积分总和。

样例

输入格式 1

1
3
3 8 10
1 4 6
6 4 5

输出格式 1

11