{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e sprinklers are\n installed in a horizontal strip of grass \u003cspan class\u003d\"tex2jax_process\"\u003e$l$\u003c/span\u003e meters long and \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e meters wide. Each sprinkler is\n installed at the horizontal center line of the strip. For each\n sprinkler we are given its position as the distance from the\n left end of the center line and its radius of operation.\u003c/p\u003e\n \u003cp\u003eWhat is the minimum number of sprinklers to turn on in order\n to water the entire strip of grass?\u003c/p\u003e\n \u003cdiv class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/3079b8c212506343d0a368b0ee35db11?v\u003d1714519982\" alt\u003d\"\\includegraphics[width\u003d0.75\\textwidth ]{grass}\" style\u003d\"width:75.00%\"\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eInput consists of at most \u003cspan class\u003d\"tex2jax_process\"\u003e$35$\u003c/span\u003e cases. The first line for each\n case contains integer numbers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$l$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e with \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n \\le 10\\, 000$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le l \\le 10^7$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le w \\le 100$\u003c/span\u003e. The next\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines contain two\n integers giving the position \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0\n \\le x \\le l$\u003c/span\u003e) and radius of operation \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le r \\le 1\\, 000$\u003c/span\u003e) of a sprinkler.\u003c/p\u003e\n \u003cp\u003eThe picture above illustrates the first case from the sample\n input.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each test case output the minimum number of sprinklers\n needed to water the entire strip of grass. If it is impossible\n to water the entire strip output \u003cspan class\u003d\"tex2jax_process\"\u003e$-1$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e8 20 2\n5 3\n4 1\n1 2\n7 2\n10 2\n13 3\n16 2\n19 4\n3 10 1\n3 5\n9 3\n6 1\n3 10 1\n5 3\n1 1\n9 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n2\n-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}