Two Yachts

A marine resort put the use of two luxury yachts up for bidding for the coming season. Everyone who takes part in the bidding submits a sealed proposal that gives a period of use and a bidding price. After the bidding closes, the manager of the resort picks proposals so that the periods of use never overlap on a single yacht, and so that the profit is as large as possible. A participant whose proposal is picked uses one yacht for the submitted period. The season consists of $m$ days numbered from 1 to $m$.

Because there are two yachts, no day may be covered by three or more of the picked periods.

Suppose there are five proposals.

The manager cannot take all five, because some days are covered by three or more periods. Picking proposals 2 and 5 gives a profit of 130,000. The largest profit comes from proposals 1, 3, and 5, and it is 180,000.

Given $n$ proposals, write a program that reports the largest profit the resort can obtain.

Your program reads from standard input. The first line holds the number of test cases $T$.

Each test case begins with the number of proposals $n$ ($1 \le n \le 10\,000$). Each of the next $n$ lines holds three integers $s$, $t$, and $p$: the beginning day of the period of use, the ending day of the period of use, and the bidding price ($1 \le s \le t \le 10\,000\,000$, $1 \le p \le 100\,000$).

You may assume that the number of proposals overlapping on the same day is at most 100.

Your program writes to standard output. Print exactly one line for each test case, holding an integer, the largest profit the resort can obtain.