요트 두 척

한 해양 리조트가 다음 시즌에 쓸 요트 두 척의 사용권을 입찰에 부친다. 입찰에 참가하는 사람은 사용 기간과 입찰 금액을 적은 제안서를 밀봉해 낸다. 입찰이 끝나면 리조트 담당자는 요트마다 사용 기간이 서로 겹치지 않도록 제안서를 골라 이익을 최대로 만든다. 제안서가 뽑힌 참가자는 자기가 적어 낸 기간 동안 요트 한 척을 쓴다. 시즌은 1번부터 $m$번까지 번호를 매긴 $m$일로 이루어진다.

요트가 두 척이므로, 어느 날에도 뽑힌 제안서의 사용 기간이 셋 이상 겹쳐서는 안 된다.

예를 들어 제안서 다섯 개가 다음과 같다고 하자.

담당자는 다섯 개를 모두 뽑을 수 없다. 세 개 이상의 기간이 겹치는 날이 생기기 때문이다. 2번과 5번을 뽑으면 이익은 130,000이다. 이익을 최대로 하려면 1번, 3번, 5번을 뽑아야 하고, 이때 이익은 180,000이다.

제안서 $n$개가 주어질 때, 이익이 최대가 되도록 제안서를 골랐을 때의 이익을 구하는 프로그램을 작성하시오.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 제안서의 개수 $n$이 주어진다 ($1 \le n \le 10\,000$). 이어지는 $n$개의 줄에는 정수 세 개 $s$, $t$, $p$가 주어진다. 차례대로 사용 기간의 시작일, 사용 기간의 종료일, 입찰 금액이다 ($1 \le s \le t \le 10\,000\,000$, $1 \le p \le 100\,000$).

같은 날에 겹치는 제안서는 100개를 넘지 않는다고 가정해도 된다.

출력은 표준 출력으로 한다. 테스트 케이스마다 한 줄씩 출력한다. 각 줄에는 리조트가 얻을 수 있는 최대 이익을 정수로 출력한다.