#P4048. [Cerc2014] Outer space invaders
[Cerc2014] Outer space invaders
题目描述
有 个外星人进攻。第 个外星人于时刻 出现,距离你 ,最晚要在时刻 消灭它。也就是说,可以消灭它的时间区间为 ,两端都可以开火。
你可以选择时刻发射冲击波,每次自行选择功率 。它会瞬间消灭所有已出现、尚未消灭且距离不超过 的外星人,同时消耗 单位燃料。
求按时消灭所有外星人需要的最少燃料。
输入格式
第一行输入数据组数 。每组先输入一个整数 ,接下来恰好 行,第 行给出 。
输出格式
每组输出一行一个整数,表示最少燃料消耗。
样例 #1
样例输入 #1
1
3
1 4 4
4 7 5
3 4 7
样例输出 #1
7
样例说明
在时刻 以功率 开火一次,可同时消灭三个外星人。
数据范围
,,。