7928: BZOJ3928：[Cerc2014] Outer space invaders

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  killed.  有N个外星人，第i个外星人会在ai时间出现，离你距离di，并且必须在bi之前被消灭。你有一把很NB的武器，攻击范围是个半径为R的圆，R可以任意调整，不过你以R的范围每攻击一次就要消耗R单位能量。外星人被攻击一次就会死掉。求需要消灭所有外星人的最小消耗能量。  N<=300, ai,bi,di<=10000 

输入格式

The first line of input contains the number of test cases T. The descriptions of the test cases  follow:  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
3
1 4 4
4 7 5
3 4 7

样例输出

7

提示

没有写明提示

题目来源

没有写明来源