{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e在“紫苑花园的色彩”活动期间,作为专业的Lady Guuji,Sayu被指派购买其中一个名为“尊贵者,雷神奥御所”的人偶。\u003cbr\u003e\u003cbr\u003e有$n$位编号从$1$到$n$的人打算购买一个人偶,商店有$m$个窗口,从$1$到$m$标识的$m$个队列。第$i$位顾客有到达时间$a_i$和购买人偶所需时间$s_i$(保证每个人的到达时间$a_i$都不同)。当一个人到达商店时,他会选择人数最少的队列排队。如果有多个人数最少的队列,他会选择标识最小的队列。值得注意的是,如果有人在同一时间离开队列,那么这个人会在所有人离开队伍后选择队列。\u003cbr\u003e\u003cbr\u003eSayu从昨晚开始就在这里等待购买人偶。但是等待等待,她的眼睛开始感到非常沉重,然后...睡过头了。如果Sayu不买这些人偶中的一个,天狼兵团的天狐将会终身监禁她!商店在这$n$位顾客购买人偶后关闭,这意味着她必须在最后一个人离开之前醒来。现在Lady Guuji想知道Sayu醒来的最晚时间。\u003cbr\u003e\u003cbr\u003e例如,同一队列中有两个人,$a_1\u003d1, s_1\u003d2, a_2\u003d2, s_2\u003d2$。当第一个人到达时,队列中没有人,因此购买人偶的开始时间和结束时间分别为$1$和$3$。当第二个人到达时,第一个人仍在队列中,因此购买人偶的开始时间和结束时间分别为$3$和$5$。如果最后一个人的结束时间为$x$,则答案为$x$。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个整数$T$ $(1 \\le T \\le 10)$。\u003cbr\u003e\u003cbr\u003e每个测试用例的第一行包含两个正整数$n$和$m$ $(1\\le n \\le 2 \\times 10^5,1\\le m \\le 2 \\times 10^5)$ --- 人数和队列数。\u003cbr\u003e\u003cbr\u003e然后,跟着$n$行,每行包含两个整数$a_i$和$s_i$ $(1\\le a_i,s_i \\le 10^9)$ --- 第$i$位顾客的到达时间和购买时间。\u003cbr\u003e\u003cbr\u003e保证$n$的总和不超过$2 \\times 10^6$,$m$的总和不超过$2 \\times 10^6$。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例:\u003cbr\u003e\u003cbr\u003e输出一行,包含一个整数 --- Sayu醒来的最晚时间,即最后一个人的结束时间。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5 3\r\n2 4\r\n1 3\r\n5 1\r\n3 4\r\n4 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}