{"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\"\u003eDo you like treasure hunting? Today, with one of his friend, iSea is on a venture trip again. As most movie said, they find so many gold hiding in their trip.\u003cbr\u003eNow iSea’s clever friend has already got the map of the place they are going to hunt, simplify the map, there are three ground types:\u003cbr\u003e\u003cbr\u003e● \u0027.\u0027 means blank ground, they can get through it\u003cbr\u003e● \u0027#\u0027 means block, they can’t get through it\u003cbr\u003e● \u0027*\u0027 means gold hiding under ground, also they can just get through it (but you won’t, right?)\u003cbr\u003e\u003cbr\u003eWhat makes iSea very delighted is the friend with him is extraordinary justice, he would not take away things which doesn’t belong to him, so all the treasure belong to iSea oneself! \u003cbr\u003eBut his friend has a request, he will set up a number of rally points on the map, namely \u0027A\u0027, \u0027B\u0027 ... \u0027Z\u0027, \u0027a\u0027, \u0027b\u0027 ... \u0027z\u0027 (in that order, but may be less than 52), they start in \u0027A\u0027, each time friend reaches to the next rally point in the shortest way, they have to meet here (i.e. iSea reaches there earlier than or same as his friend), then start together, but you can choose different paths. Initially, iSea’s speed is the same with his friend, but to grab treasures, he save one time unit among each part of road, he use the only one unit to get a treasure, after being picked, the treasure’s point change into blank ground.\u003cbr\u003eUnder the premise of his friend’s rule, how much treasure iSea can get at most?\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases in the input.\u003cbr\u003e\u003cbr\u003eEach test case begin with two integers R, C (2 ≤ R, C ≤ 100), indicating the row number and the column number.\u003cbr\u003eThen R strings follow, each string has C characters (must be ‘A’ – ‘Z’ or ‘a’ – ‘z’ or ‘.’ or ‘#’ or ‘*’), indicating the type in the coordinate.\u003cbr\u003e\u003cbr\u003eThe input terminates by end of file marker.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one integer, indicating maximum gold number iSea can get, if they can’t meet at one or more rally points, just output -1.\u003cbr\u003e\u003cbr\u003e"}},{"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\u003e2 4\r\nA.B.\r\n***C\r\n2 4\r\nA#B.\r\n***C\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}