TV 전쟁

집에 티비가 한 대뿐이라 가족이 어떤 프로그램을 볼지 늘 다툰다. 이 다툼을 자동으로 정리해 주는 기계를 만들려고 한다.

한 해 동안 가족이 보려는 프로그램은 이미 정해져 있다. 각 프로그램은 매주 같은 시각에 시작해서 같은 시각에 끝나므로, 한 주 분량의 시청 계획만 세워 두면 1년 내내 그대로 쓰면 된다. 프로그램마다 가족이 매긴 선호도 점수가 있고, 점수가 높을수록 가족이 더 보고 싶어 하는 프로그램이다. 티비가 한 대뿐이라 시간이 겹치는 두 프로그램을 함께 볼 수는 없다.

시청 시간이 서로 겹치지 않게 프로그램을 고를 때, 선호도의 총합이 최대가 되도록 하려고 한다. 그 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다.

각 테스트 케이스의 첫 줄에는 프로그램의 개수 $n$ $(1 \le n \le 100000)$이 주어진다. 이어지는 $n$개의 줄에는 공백으로 구분된 정수 $s$, $d$, $p$가 주어진다. $s$는 프로그램이 시작하는 시각, $d$는 프로그램이 이어지는 시간, $p$는 그 프로그램의 선호도이다. $(0 \le s < s+d \le 10080,\ 1 \le p \le 2000)$

$s+d$를 $k$라고 하면 이 프로그램은 정확히 $k$ 시각에 끝나고, 다른 프로그램을 정확히 $k$ 시각부터 볼 수 있다.

각 테스트 케이스마다 선호도 총합의 최댓값을 한 줄에 출력한다.

첫 번째 예제에서 시각 $1$에 시작해 $4$만큼 이어지는 프로그램과 시각 $6$에 시작해 $4$만큼 이어지는 프로그램을 고르면 선호도의 합이 $6+5=11$이고, 이것이 가족이 얻을 수 있는 최댓값이다.