{"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\u003eThe spaceship «Enterprise» has got into meteor flow and is under threat of destruction. Once this happens, Captain Kirk ordered to switch the force shield on, and onboard computer instantly determined \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e meteors which give no chance to be evaded. Assuming the force shield is switched on at the moment \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e, it is known that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th meteor will strike the «Enterprise» at the moment \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and deal \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e units of damage.\u003c/p\u003e\u003cp\u003eEach unit of time the force shield increases its power by \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. When the meteor strikes the «Enterprise», the ship receives damage if the power of the shield is less than the meteor\u0027s damage. Otherwise, the power of the force shield decreases by the meteor\u0027s damage.\u003c/p\u003e\u003cp\u003eThe «Enterprise» has a cannon, each shot of which can knock any meteor off. But Captain Kirk does not like unnecessary firing and wants to overcome the meteor flow without any damage received and doing as few shots as possible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 200000\u003c/span\u003e)\u0026nbsp;— the number of meteors.\u003c/p\u003e\u003cp\u003eThen \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines follow. Each of them contains two integers separated by space: \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\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\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ed\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)\u0026nbsp;— the moment of time when \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th meteor will strike the ship and the damage it will deal. All \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are pairwise distinct and given in ascending order.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer\u0026nbsp;— the minimal number of shots that needs to be done in order to not receive any damage.\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\n3 2\n5 4\n6 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\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\u003e5\n1 2\n3 2\n5 3\n6 2\n7 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}