{"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\u003e岡部喜欢在城市里走一条由路灯照亮的路。这样,他就不会被学生欺负。\u003c/p\u003e\u003cp\u003e岡部的城市由一个二维单元格网格表示。行从上到下编号为\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e到\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e,列从左到右编号为\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e到\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e。城市中正好有\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e个单元格由路灯照亮。保证左上角的单元格是照亮的。\u003c/p\u003e\u003cp\u003e岡部从左上角单元格开始走,想要到达右下角单元格。当然,岡部只会走在被照亮的单元格上,并且只能向上、下、左、右四个方向移动到相邻的单元格。然而,岡部还可以每次支付\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e个硬币,临时点亮一整行或一整列的所有单元格,以便走过一些最初没有被照亮的单元格。\u003c/p\u003e\u003cp\u003e请注意,岡部每次只能点亮一整行或一整列,并且每次点亮新的行或列都需要支付一个硬币。要更改临时点亮的行或列,他必须站在最初被照亮的单元格上。此外,一旦他取消对一行或列的临时点亮,那么该行/列中最初没有被照亮的所有单元格现在都不再被照亮。\u003c/p\u003e\u003cp\u003e帮助岡部找出完成他的行走所需支付的最少硬币数!\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含三个用空格分隔的整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e, \u003ci\u003ek\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e\u003c/span\u003e)。\u003c/p\u003e\u003cp\u003e接下来的每一行包含两个用空格分隔的整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\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\"\u003e\u003ci\u003ec\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\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e)— 第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e个被照亮单元格的行和列。\u003c/p\u003e\u003cp\u003e保证所有\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e个被照亮的单元格是不同的。保证左上角的单元格是被照亮的。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出岡部完成行走所需支付的最少硬币数,如果不可能完成,则输出\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e。\u003c/p\u003e"}},{"title":"示例1","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 4 5\n1 1\n2 1\n2 3\n3 3\n4 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"}},{"title":"示例2","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 5 4\n1 1\n2 1\n3 1\n3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例3","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\u003e2 2 4\n1 1\n1 2\n2 1\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例4","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 5 4\n1 1\n2 2\n3 3\n4 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例测试中,岡部可以走的路径为\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/f0d0a0ceaef4c2c4daeaed805d130ac4?v\u003d1709724533\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e,只需在移动到\u003cspan class\u003d\"tex-span\"\u003e(2, 3)\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e(4, 4)\u003c/span\u003e时支付硬币。\u003c/p\u003e\u003cp\u003e在第四个示例中,岡部可以走的路径为\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a134c0bad9dd2eff385aa66d8ae301d3?v\u003d1709724533\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a410d4b6900b3b674c8f3310616d8d3d?v\u003d1709724533\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e,在移动到\u003cspan class\u003d\"tex-span\"\u003e(1, 2)\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e(3, 4)\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e(5, 4)\u003c/span\u003e时支付硬币。\u003c/p\u003e"}}]}