#4048. [Cerc2014] Outer space invaders

[Cerc2014] Outer space invaders

题目描述

来自外太空的外星人(最终)入侵了地球。保卫自己,或者解体,被他们同化,或者成为食物。迄今为止,我们无法确定。

外星人遵循已知的攻击模式。有 nn 个外星人进攻,第 ii 个进攻的外星人会在时间 aia_i 出现,距离你的距离为 did_i,它必须在时间 bib_i 前被消灭,否则被消灭的会是你。

你的武器是一个区域冲击波器,可以设置任何给定的功率。如果被设置了功率 RR,它会瞬间摧毁与你的距离在 RR 以内的所有外星人(可以等于),同时它也会消耗 RR 单位的燃料电池。

求摧毁所有外星人的最低成本(消耗多少燃料电池),同时保证自己的生命安全。

输入格式

多组数据,第一行一个整数 TT 表示数据组数。

每组数据的第一行包括一个数 nn,接下来 n+1n+1 行,每行有三个数 ai,bi,dia_i,b_i,d_i,表示这个外星人在时间 aia_i 出现,距离你 did_i,在 bib_i 前时刻死亡。

输出格式

TT 行,每行一个整数表示摧毁所有外星人的最低成本。

1
3
1 4 4
4 7 5
3 4 7
7

数据范围

对于 100%100\% 的数据,1n300,ai,bi,di1041\le n\le 300,a_i,b_i,d_i\le 10^4