{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\u003cp\u003eYou are playing a solitaire puzzle called \"Connect\", which uses several letter tiles.\n\u003c/p\u003e\n\u003cp\u003eThere are \u003cvar\u003eR × C\u003c/var\u003e empty cells.\nFor each \u003cvar\u003ei\u003c/var\u003e \u003cvar\u003e(1 ≤ i ≤ R)\u003c/var\u003e, you must put a string \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003e(1 ≤ |s\u003csub\u003ei\u003c/sub\u003e| ≤ C)\u003c/var\u003e in the \u003cvar\u003ei\u003c/var\u003e-th row of the table, without changing the letter order.\nIn other words, you choose an integer sequence \u003cvar\u003e{a\u003csub\u003ej\u003c/sub\u003e}\u003c/var\u003e such that\n\u003cvar\u003e1 ≤ a\u003csub\u003e1\u003c/sub\u003e \u0026lt; a\u003csub\u003e2\u003c/sub\u003e \u0026lt; ... \u0026lt; a\u003csub\u003e|s\u003csub\u003ei\u003c/sub\u003e|\u003c/sub\u003e ≤ C\u003c/var\u003e\n, and put the \u003cvar\u003ej\u003c/var\u003e-th character of the string \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e in the \u003cvar\u003ea\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e-th column \u003cvar\u003e(1 ≤ j ≤ |s\u003csub\u003ei\u003c/sub\u003e|)\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003eFor example, when \u003cvar\u003eC \u003d 8\u003c/var\u003e and \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e \u003d\u003c/var\u003e \"ICPC\", you can put \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e like followings.\n\u003c/p\u003e\u003cpre\u003eI_C_P_C_\nICPC____\n_IC___PC\n\u003c/pre\u003e\u003cp\u003e\u0027_\u0027 represents an empty cell.\n\u003c/p\u003e\n\u003cp\u003eFor each non-empty cell \u003cvar\u003ex\u003c/var\u003e, you get a point equal to the number of adjacent cells which have the same character as \u003cvar\u003ex\u003c/var\u003e.\nTwo cells are adjacent if they share an edge.\n\u003c/p\u003e\n\u003cp\u003eCalculate the maximum total point you can get.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe first line contains two integers \u003cvar\u003eR\u003c/var\u003e and \u003cvar\u003eC\u003c/var\u003e \u003cvar\u003e(1 ≤ R ≤ 128, 1 ≤ C ≤ 16)\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003e Then \u003cvar\u003eR\u003c/var\u003e lines follow, each of which contains \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e\n \u003cvar\u003e(1 ≤ |s\u003csub\u003ei\u003c/sub\u003e| ≤ C)\u003c/var\u003e.\nAll characters of \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e are uppercase letters.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003eOutput the maximum total point in a line.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e2 4\nACM\nICPC\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e2\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e2 9\nPROBLEMF\nCONNECT\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e6\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e4 16\nINTERNATIONAL\nCOLLEGIATE\nPROGRAMMING\nCONTEST\n\u003c/pre\u003e\n\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e18\n\u003c/pre\u003e\n"}}]}