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

外星人遵循已知的攻击模式。有N个外星人进攻，第i个进攻的外星人会在时间ai出现，距离你的距离为d i ,它必须在时间b _i _ 前被消灭，否则被消灭的会是你。

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

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

输入格式：

第一行输入一个数T,表示有T组数据

每组数据的第一行为外星人的数量n（1<=n<=300)

接下来n+1行，每行有三个数ai,bi,di，表示这个外星人在时间ai出现，距离你di,在bi时刻死亡

输出格式：

每组输出摧毁所有外星人的最低成本