{"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\"\u003eIt’s harvest season now! \u003cbr\u003eFarmer John plants a lot of corn. There are many birds living around his corn field. These birds keep stealing his corn all the time. John can\u0027t stand with that any more. He decides to put some scarecrows in the field to drive the birds away. \u003cbr\u003eJohn\u0027s field can be considered as an N×N grid which has N×N intersections. John plants his corn on every intersection at first. But as time goes by, some corn were destroyed by rats or birds so some vacant intersections were left. Now John wants to put scarecrows on those vacant intersections and he can put at most one scarecrow on one intersection. Because of the landform and the different height of corn, every vacant intersections has a scaring range R meaning that if John put a scarecrow on it, the scarecrow can only scare the birds inside the range of manhattan distance R from the intersection.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/a084676bfccba352c19e5ab630518a5e?v\u003d1726318847\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eThe figure above shows a 7×7 field. Assuming that the scaring range of vacant intersection (4,2) is 2, then the corn on the marked intersections can be protected by a scarecrow put on intersection (4,2). \u003cbr\u003eNow John wants to figure out at least how many scarecrows he must buy to protect all his corn.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases. \u003cbr\u003eFor each test case: \u003cbr\u003eThe first line is an integer N ( 2 \u0026lt;\u003d N \u0026lt;\u003d 50 ) meaning that John\u0027s field is an N×N grid. \u003cbr\u003eThe second line is an integer K ( 0\u0026lt;\u003d K \u0026lt;\u003d 10) meaning that there are K vacant intersections on which John can put a scarecrow.\u003cbr\u003eThe third line describes the position of K vacant intersections, in the format of r\u003csub\u003e1\u003c/sub\u003e,c\u003csub\u003e1\u003c/sub\u003e,r\u003csub\u003e2\u003c/sub\u003e,c\u003csub\u003e2\u003c/sub\u003e …. r\u003csub\u003eK\u003c/sub\u003e,c\u003csub\u003ek\u003c/sub\u003e . (r\u003csub\u003ei\u003c/sub\u003e,c\u003csub\u003ei\u003c/sub\u003e) is the position of the i-th intersection and 1 \u0026lt;\u003d r\u003csub\u003e1\u003c/sub\u003e,c\u003csub\u003e1\u003c/sub\u003e,r\u003csub\u003e2\u003c/sub\u003e,c\u003csub\u003e2\u003c/sub\u003e …. r\u003csub\u003eK\u003c/sub\u003e,c\u003csub\u003ek\u003c/sub\u003e \u0026lt;\u003d N. \u003cbr\u003eThe forth line gives the scaring range of all vacant intersections, in the format of R\u003csub\u003e1\u003c/sub\u003e,R\u003csub\u003e2\u003c/sub\u003e…R\u003csub\u003eK\u003c/sub\u003e and 0 \u0026lt;\u003d R\u003csub\u003e1\u003c/sub\u003e,R\u003csub\u003e2\u003c/sub\u003e…R\u003csub\u003eK\u003c/sub\u003e \u0026lt;\u003d 2 × N. \u003cbr\u003eThe input ends with N \u003d 0."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the minimum number of scarecrows farmer John must buy in a line. If John has no way to protect all the corn, print -1 instead."}},{"title":"Sample","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\u003e4\r\n2\r\n2 2 3 3\r\n1 3\r\n4\r\n2\r\n2 2 3 3\r\n1 4\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}