外太空侵略者

题目描述

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

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

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

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

输入

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

每组数据的第一行为外星人的数量 n（1\leq n\leq 300）。

接下来 n 行，每行有三个数 a_i,b_i,d_i，表示这个外星人在时间 a_i 出现，距离你 d_i，在 b_i 前时刻死亡。

输出

共 T 行，每行输出摧毁所有外星人的最低成本。

样例

提示

1 \le n \le 300 ，1 \le T \le 20， 1 \le a_i < b_i \le 10 000, 1 \le d_i \le 10 000

来源

CERC