#P9196. Buy Figurines

    ID: 5265 传统题 6000ms 256MiB 尝试: 4 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-事件驱动模拟优先队列调度事件有序集合同时事件分阶段处理2022杭电多校

Buy Figurines

Buy Figurines

题目描述

在「堇庭华彩」活动期间,早柚受宫司大人雇用,被指派购买一尊「御建鸣神主尊大御所大人像」。

有 nn 个人想要购买手办,编号为 11 到 nn。商店有 mm 个窗口,对应的队伍编号为 11 到 mm。第 ii 个人的到达时间为 aia_i,购买手办所需的时间为 sis_i。保证所有人的到达时间 aia_i 互不相同。

当一个人到达商店时,他会选择人数最少的队伍排队。如果有多个队伍的人数同为最少,他会选择编号最小的队伍。需要注意,如果同一时刻有人离开队伍,则到达的人会在该时刻所有应离开的人离开后,再选择队伍。每个窗口按先来后到的顺序服务,正在购买的人仍计入该队的人数。

早柚从昨晚就来到这里,以便买到手办。但等着等着,她的眼皮开始打架,然后……睡过头了。如果早柚没能买到手办,天领奉行的天狗就会把她关上一辈子!商店会在这 nn 个人都买完手办后关门,宫司大人想知道商店关门的时刻,也就是最后一个人购买完成的时刻。

例如,同一队伍中有两个人,a1=1,s1=2,a2=2,s2=2a_1=1,s_1=2,a_2=2,s_2=2。第一个人到达时,队伍中没有人,所以他购买手办的开始时间和结束时间分别为 11 和 33。第二个人到达时,第一个人仍在队伍中,所以他购买手办的开始时间和结束时间分别为 33 和 55。如果最后一个人的结束时间为 xx,那么答案就是 xx。

输入格式

第一行包含一个整数 TT(1≤T≤101\le T\le 10),表示测试用例数。

每个测试用例的第一行包含两个正整数 nn 和 mm(1≤n≤2×1051\le n\le 2\times 10^5,1≤m≤2×1051\le m\le 2\times 10^5),分别表示人数和队伍数。

接下来 nn 行,每行包含两个整数 aia_i 和 sis_i(1≤ai,si≤1091\le a_i,s_i\le 10^9),分别表示第 ii 个人的到达时间和购买所需时间。

保证所有测试用例的 nn 之和不超过 2×1062\times 10^6,mm 之和不超过 2×1062\times 10^6。

输出格式

对于每个测试用例,输出一行一个整数,表示早柚最晚醒来的时间,即最后一个人购买结束的时间。

样例

1
5 3
2 4
1 3
5 1
3 4
4 2
7

来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。

原 PDF 题面