Problem: You are playing a solitaire puzzle called "Connect", which uses several letter tiles.

There are R × C empty cells. For each i (1 ≤ i ≤ R), you must put a string si (1 ≤ |si| ≤ C) in the i-th row of the table, without changing the letter order. In other words, you choose an integer sequence {aj} such that 1 ≤ a1 < a2 < ... < a|si| ≤ C , and put the j-th character of the string si in the aj-th column (1 ≤ j ≤ |si|).

For example, when C = 8 and si = "ICPC", you can put si like followings.


I_C_P_C_
ICPC____
_IC___PC


'_' represents an empty cell.

For each non-empty cell x, you get a point equal to the number of adjacent cells which have the same character as x. Two cells are adjacent if they share an edge.

Calculate the maximum total point you can get.



Input

The first line contains two integers R and C (1 ≤ R ≤ 128, 1 ≤ C ≤ 16).

Then R lines follow, each of which contains si (1 ≤ |si| ≤ C). All characters of si are uppercase letters.

Output

Output the maximum total point in a line.

Examples

Input

2 4
ACM
ICPC


Output

2


Input

2 9
PROBLEMF
CONNECT


Output

6


Input

4 16
INTERNATIONAL
COLLEGIATE
PROGRAMMING
CONTEST


Output

18

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define R 128
#define C 16

int r, c;
string ss[R];

int dp[2][1 << C];
int bc[1 << C], mask[C+1];

int solve() {
  string &s1 = ss[0];
  int l1 = s1.size();
  repl(j, 1, c-1) {
    int b0 = 1 << (j-1);
    int b1 = 1 << j;
    rep(state, (1 << j)) {
      int lc = bc[state];
      if(l1-lc < c-j) {
        dp[1][state] = max(dp[1][state], dp[0][state]);
      }
      if(lc < l1) {
        int n_state = state | b1;
        if((state & b0) && (s1[lc-1] == s1[lc])) {
          dp[1][n_state] = max(dp[1][n_state], dp[0][state] + 2);
        } else {
          dp[1][n_state] = max(dp[1][n_state], dp[0][state]);
        }
      }
    }
    rep(k, (1 << (j+1))) dp[0][k] = dp[1][k], dp[1][k] = 0;
  }
  repl(i, 1, r-1) {
    string &s0 = ss[i-1], &s1 = ss[i];
    int l0 = s0.size(), l1 = s1.size();
    rep(j, c) {
      int b0 = (j > 0 ? 1 << (j-1) : 0);
      int b1 = (1 << j);
      int k = i*c + j;
      rep(state, (1 << c)) {
        int lc = bc[state & mask[j]], rc = bc[state] - lc;
        if(l1-lc < 0 || c-j < l1-lc) continue;
        if(l0-rc < 0 || j < l0-rc) continue;

        int n_state = (state & b1) ? (state ^ b1) : state;
        if(l1-lc < c-j) {
          dp[1][n_state] = max(dp[1][n_state], dp[0][state]);
        }
        if(lc < l1) {
          int x = 0;
          n_state |= b1;
          if((state & b0) && s1[lc-1] == s1[lc]) x += 2;
          if((state & b1) && s0[l0-rc] == s1[lc]) x += 2;
          dp[1][n_state] = max(dp[1][n_state], dp[0][state] + x);
        }
      }
      rep(k, (1 << c)) dp[0][k] = dp[1][k], dp[1][k] = 0;
    }
  }
  int ans = 0;
  rep(i, (1 << c)) {
    ans = max(ans, dp[0][i]);
  }
  return ans;
}

int main() {
  cin >> r >> c;
  repl(i, 1, (1 << c)-1) bc[i] = bc[i ^ (i & -i)] + 1;
  rep(i, c) mask[i+1] = mask[i] | (1 << i);

  rep(i, r) cin >> ss[i];
  cout << solve() << endl;
  return 0;
}