火焰与铁蹄之路

题目描述

西元 1403 年，波希米亚王国正被战火撕裂。瓦茨拉夫国王被囚，异族军队如潮水般涌入乡野。 在屠戮、抢掠、烧毁的阴影之下，幸存的村民四散逃亡，贵族仍在权力的夹缝中苟延残喘。

你 —— 亨利（Henry）， 一个铁匠的儿子，一个在战火中侥幸活下来的难民， 被拉泰城的汉斯领主收留，加入民兵团，肩负守护城镇的责任。

然而敌军并未给你喘息的机会。

---

⚔️ 敌军突袭 —— 弱小城镇的生死考验

敌军分成数支突袭队，像野狼般徘徊在波希米亚的林间道路上。 每支部队都有不同的行动方式 ——

• 有的像狂暴的马贼，疾驰而来；
• 有的像潜行的猎手，伺机而动；
• 有的携带燃烧罐，意图点燃整个拉泰城。

守军兵力单薄，粮草不足。 城墙修补不及，训练匆忙，普通农民根本无法在战场上坚持几秒钟。

你被分派去处理高度危险的任务：

你需要决定：在有限的时间与资源下，应该拦截哪些敌人？

每一次拦截行动：

• 需要调动弓手或骑兵
• 消耗大量体力
• 若决策错误，将直接导致城镇失陷

指挥官罗布伯爵对你说：

“亨利，我们拦不住所有敌人。 你必须判断哪一支敌军最具有威胁，并优先解决他们。 我们只能依靠你的判断了。”

---

🛡️ 战术策略：抓住最危险的敌军

每支敌军：

• 有 预计到达时间
• 有 威胁值（反映人数、装备、指挥、战术水平）

你最多可以组织 k 次拦截行动。 每一次行动都需要提前准备，只能在敌军到达之后执行。

城镇将会按照你的选择布置伏击、封锁道路、派出骑兵包抄…… 但由于资源稀缺，所有布置都只够 最多拦截 k 支敌军。

拦截时机你可以自定： 夜晚、清晨、林间伏击、桥头封锁…… 只要那支敌军已经抵达指定区域即可实施行动。

但你无法更改一个事实：

不能拦截全部敌军，你必须从中选择最危险的那些。

成功与否，决定的是拉泰城的命运。

---

🩸 失败的后果

若选择错误：

• 村庄可能被洗劫
• 商队将被劫杀
• 城墙可能被点燃
• 教堂将被破坏
• 平民将四散逃亡
• 人心将涣散

而你 —— 也可能背负责备、痛苦与无尽的悔恨。

---

🏹 你的任务：最大化拦截威胁总值

作为指挥官，你要制定拦截计划，最终目标是：

拦截最多 k 支威胁最高的敌军，拯救拉泰城。

你能否在这场混乱里，让火焰不再蔓延？ 你能否用有限的力量改变城镇的命运？

这是你的火焰试炼。 愿上帝与你同在。

---

有n支敌军部队，你有k次拦截机会，每只敌军部队的到达时间为t，威胁值是v。

你需要选择最多 k 支敌军，使得它们的总威胁值最大，并满足：

1. 如果你选择了一支到达时间为 $t$ 的敌军，你必须设置一个拦截时间 $T \ge t$。

总结成一句：

你最多选 k 个敌军，这 k 个敌军的到达时间可以任意安排在时间线上，只要各自不早于它到达的时刻。求最大总威胁值。

输入格式

输入一个整数 T（$1 \leq T \leq 10^4$），表示样例组数。

• 每组样例中，输入两个整数 n 和 k（$1 \leq k \leq n \leq 10^{6}$）。
• 接下来 n 行，每行输入 $t_i$ 和 $v_i$（$1 \leq t_i,v_i \leq 10^9$），表示到达时间和威胁值。

保证所有测试数据中 $n$ 之和不超过 $10^6$。

输出格式

输出T行，每行输出最大可拦截的总威胁值。

样例 1

1
5 2
1 5
3 2
4 4
2 6
3 1

11

提示

亨利可以选择到达时间为 1 和 2 的两支敌军，总威胁值 = 5 + 6 = 11，这是最优选择。