来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。
外星人遵循已知的攻击模式。有 个外星人进攻，第 个进攻的外星人会在时间 出现，距离你的距离为 ，它必须在时间 前被消灭，否则被消灭的会是你。
你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 ，它会瞬间摧毁与你的距离在 RR 以内的所有外星人（可以等于），同时它也会消耗 单位的燃料电池。
求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。
多组数据，第一行一个整数 表示数据组数。
每组数据的第一行包括一个数 ，接下来 行，每行有三个数 ，表示这个外星人在时间 出现，距离你 ，在 前时刻死亡。
共 行，每行一个整数表示摧毁所有外星人的最低成本。
1 3 1 4 4 4 7 5 3 4 7
7
对于 的数据，。
