#P9196. Buy Figurines
Buy Figurines
Buy Figurines
题目描述
在「堇庭华彩」活动期间,早柚受宫司大人雇用,被指派购买一尊「御建鸣神主尊大御所大人像」。
有 个人想要购买手办,编号为 到 。商店有 个窗口,对应的队伍编号为 到 。第 个人的到达时间为 ,购买手办所需的时间为 。保证所有人的到达时间 互不相同。
当一个人到达商店时,他会选择人数最少的队伍排队。如果有多个队伍的人数同为最少,他会选择编号最小的队伍。需要注意,如果同一时刻有人离开队伍,则到达的人会在该时刻所有应离开的人离开后,再选择队伍。每个窗口按先来后到的顺序服务,正在购买的人仍计入该队的人数。
早柚从昨晚就来到这里,以便买到手办。但等着等着,她的眼皮开始打架,然后……睡过头了。如果早柚没能买到手办,天领奉行的天狗就会把她关上一辈子!商店会在这 个人都买完手办后关门,宫司大人想知道商店关门的时刻,也就是最后一个人购买完成的时刻。
例如,同一队伍中有两个人,。第一个人到达时,队伍中没有人,所以他购买手办的开始时间和结束时间分别为 和 。第二个人到达时,第一个人仍在队伍中,所以他购买手办的开始时间和结束时间分别为 和 。如果最后一个人的结束时间为 ,那么答案就是 。
输入格式
第一行包含一个整数 (),表示测试用例数。
每个测试用例的第一行包含两个正整数 和 (,),分别表示人数和队伍数。
接下来 行,每行包含两个整数 和 (),分别表示第 个人的到达时间和购买所需时间。
保证所有测试用例的 之和不超过 , 之和不超过 。
输出格式
对于每个测试用例,输出一行一个整数,表示早柚最晚醒来的时间,即最后一个人购买结束的时间。
样例
1
5 3
2 4
1 3
5 1
3 4
4 2
7
来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。