The aliens from outer space have (finally!) invaded Earth. Defend yourself, or be disintegrated!
Or assimilated. Or eaten. We are not yet sure.
The aliens follow a known attack pattern. There are 'n attackers, the i-th one appears at time
ai, at distance di from you. He must be destroyed no later than at time bi, or else he will fire his
weapon, which will definitely end the fight.
Your weapon is an area-blaster, which can be set to any given power. If fired with power R,
it momentarily destroys all aliens at distance R or smaller. It also consumes R fuel cells.
Determine the minimal cost (measured in fuel cells) of destroying all the aliens, without being
The first line of input contains the number of test cases T. The descriptions of the test cases
Each test case starts with a line containing the number of aliens n (1《 n≤ 300). Of the next
n lines, the i-th one contains three integers ai, bi, di, (1 < ai < bi≤ 10 000; I < di≤ 10 000).
The i-th alien appears at time ai, is idle until bi, and his distance from vou is di.
For each test case, output one line containing the mimmum number of cells needed to destrov
all the aliens.
1 4 4
4 7 5
3 4 7