Problem I: 炸弹人

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $18$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 模拟 动态规划

Description

炸弹人想要炸毁A城市。A城市是一条直线段，有n个炸弹安放点，分别编号1..n。炸弹人手里有m个不同的定时炸弹，第i个炸弹的威力是，延时时间是秒，一旦炸弹被安放，等炸弹的延时时间一过，这个炸弹就会立即爆炸，炸弹只能爆炸一次。炸弹爆炸时，处在其威力范围内的其他炸弹会被摧毁，失去爆炸的能力（如果炸弹的位置是p，威力是w，[p-w,p+w]都算炸弹的威力范围）。由于炸弹人的头脑不够发达，他决定按照一个预先指定好的计划进行炸弹安放任务。这个计划一共包含m条指令，每条指令指出了要安放的炸弹的位置和具体要安放哪一个。炸弹人从1号位置出发，从一个点走到相邻的另一个点耗费1秒，如果某个炸弹爆炸时炸弹人刚好处在炸弹的威力范围中则会立刻死亡，过1秒，炸弹人会原地满血复活，接着上一次未完成的任务继续完成任务（炸弹人未安放的炸弹不会损毁），而他之前安放的炸弹仍然有效，如果它复活时刚好又被炸到，则其会立刻死亡，往后同理。

Input

第一行输入正整数T，表示数据的组数。

对于每组数据，第一行两个整数n,m(0 <=n,m <=100000 )

接下来m 行按顺序给出炸弹安放计划表， 每行3 个整数分别为wi, ti, pi( ∀݅ ∈1. . n |0<wi , ti<=1000，0<=pi<=n)，分别计划表中第i 个炸弹的威力，炸弹的延时时间，炸弹的安放位置。

Output

对于每组数据，输出一行，格式为'Case #t: x'，t 为数据的组号，x 为题目要求的结果。

Sample Input复制

1
3 3
2 1 2
1 1 1
1 1 3

Sample Output复制

Case 1: 6