{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA social network for dogs called DH (DogHouse) has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.\u003c/p\u003e\u003cp\u003eWe know that each server takes one second to recompress a one minute fragment. Thus, any server takes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e seconds to recompress a \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e minute video.\u003c/p\u003e\u003cp\u003eWe know the time when each of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.\u003c/p\u003e\u003cp\u003eFor each video find the moment it stops being recompressed.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003ek\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — the number of videos and servers, respectively.\u003c/p\u003e\u003cp\u003eNext \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contain the descriptions of the videos as pairs of integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003em\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003em\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the time in seconds when the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th video appeared and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is its duration in minutes. It is guaranteed that all the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u0027s are distinct and the videos are given in the chronological order of upload, that is in the order of increasing \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e numbers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ee\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ee\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the time in seconds after the servers start working, when the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th video will be recompressed.\u003c/p\u003e"}},{"title":"Examples","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\u003e3 2\n1 5\n2 5\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n7\n11\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e6 1\n1 1000000000\n2 1000000000\n3 1000000000\n4 1000000000\n5 1000000000\n6 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1000000001\n2000000001\n3000000001\n4000000001\n5000000001\n5000000004\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}