#P4048. [Cerc2014] Outer space invaders

    ID: 3250 传统题 2000ms 128MiB 尝试: 160 已通过: 85 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划区间 DP排序与序列处理离散化贪心极端元素优先处理CF2200

[Cerc2014] Outer space invaders

题目描述

有 nn 个外星人进攻。第 ii 个外星人于时刻 aia_i 出现,距离你 did_i,最晚要在时刻 bib_i 消灭它。也就是说,可以消灭它的时间区间为 [ai,bi][a_i,b_i],两端都可以开火。

你可以选择时刻发射冲击波,每次自行选择功率 RR。它会瞬间消灭所有已出现、尚未消灭且距离不超过 RR 的外星人,同时消耗 RR 单位燃料。

求按时消灭所有外星人需要的最少燃料。

输入格式

第一行输入数据组数 TT。每组先输入一个整数 nn,接下来恰好 nn 行,第 ii 行给出 ai,bi,dia_i,b_i,d_i。

输出格式

每组输出一行一个整数,表示最少燃料消耗。

样例 #1

样例输入 #1

1
3
1 4 4
4 7 5
3 4 7

样例输出 #1

7

样例说明

在时刻 44 以功率 77 开火一次,可同时消灭三个外星人。

数据范围

1≤n≤3001\le n\le300,1≤ai<bi≤1041\le a_i<b_i\le10^4,1≤di≤1041\le d_i\le10^4。