{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe prime minister of Berland decided to build a new city in the country. It\u0027s hard to describe the excitement of all Berland citizens, but indeed this is great news from the economic, social and cultural standpoints.\u003c/p\u003e\u003cp\u003eThe land in Berland is occupied almost entirely and it\u0027s very hard to find free space for construction, so it was decided to build the city on a stony terrain. The map of this terrain is represented as an \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e × \u003ci\u003em\u003c/i\u003e\u003c/span\u003e grid, where each cell of the grid is either an empty space or a rock.\u003c/p\u003e\u003cp\u003eOf course, before construction is started, the given terrain must be completely cleared from rocks. As you may guess, you were hired to complete this mission. Your goal is to destroy all rocks by dropping bombs from a plane. A bomb can be dropped on any cell of the map, and you are free to select where you want to drop each bomb. When a bomb targeted for cell (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e) reaches the ground, it destroys all rocks in row \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and also all rocks in column \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e of the grid. If cell (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e) contains a rock, this rock is also destroyed.\u003c/p\u003e\u003cp\u003ePlease help the prime minister of Berland to find the minimum number of bombs required to completely clear the given terrain from rocks.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 25\u003c/span\u003e)\u0026nbsp;— the number of rows and columns correspondingly. Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e characters describing the terrain. An empty space is denoted by \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e.\u003c/span\u003e\", while a rock is denoted by \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e*\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eWrite a single integer to the output — the minimum numbers of bombs required for destroying all rocks on the terrain.\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\u003e8 10\n..........\n..***..*.*\n.*.......*\n.*.......*\n.*.......*\n.....*****\n..........\n.........*\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\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\u003e3 4\n....\n....\n....\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample test it\u0027s only required to drop 2 bombs from a plane: one bomb to cell (2,2) and another bomb to cell (6, 10). Row and column indices in this explanation are 1-based.\u003c/p\u003e"}}]}