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<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

int R,C,dp[2][(1<<16)],len[130];
string s[130];
int bitcount[(1<<16)];

int main(){

  cin >> R >> C;
  rep(i,R){
    cin >> s[i];
    len[i] = (int)s[i].size();
  }

  rep(i,(1<<C))bitcount[i] = __builtin_popcount(i);
  rep(i,(1<<C))dp[0][i] = -1;
  dp[0][0] = 0;

  int answer = 0;
  rep(r,R)rep(c,C){

    int phase = ( (c+r*C) & 1 );
    int next_phase = !phase;

    rep(i,(1<<C))dp[next_phase][i] = -1;

    rep(state,(1<<C)){
      if( dp[phase][state] == -1 ) continue;
      int next_state = state & (~(1<<c));
      int bitmask = (1<<c)-1;
      int bits_L = bitcount[bitmask&state];//__builtin_popcount(bitmask&state);
      int bits_R = bitcount[state]-bits_L;//__builtin_popcount(state)-bits_L;

      if( ( r-1 >= 0 && bits_R > len[r-1] ) || ( r-1>=0 && c+bits_R < len[r-1] ) ) continue; 
      if( bits_L > len[r] || ( C-c+bits_L < len[r] ) ) continue;

      dp[next_phase][next_state] = max(dp[next_phase][next_state],dp[phase][state]);
      answer = max(answer,dp[next_phase][next_state]);

      next_state |= (1<<c);
      int score = 0;
      char char_M = s[r][bits_L];
      if( r-1 >= 0 && bits_R <= len[r-1] && c+bits_R >= len[r-1] ){
	if( bits_R > 0 && ((state>>c)&1) ){
	  char char_R = s[r-1][len[r-1]-bits_R];
	  if( char_M == char_R ) score++;
	}
      }

      if( c-1 >= 0 && bits_L < len[r] && C-c+bits_L >= len[r] ){
	if( bits_L > 0 && ((state>>(c-1))&1) ){
	  char char_L = s[r][bits_L-1];
	  if( char_L == char_M ) score++;
	}
      }

      dp[next_phase][next_state] = max(dp[next_phase][next_state],dp[phase][state]+score);
      answer = max(answer,dp[next_phase][next_state]);

    }
  }
  cout << answer*2 << endl;

  /*
    rep(r,R)rep(c,C){
    int phase = ((c+r*C)&1);
    int next_phase = !phase;
    rep(i,(1<<C))dp[next_phase][i] = 0;
    rep(state,(1<<C)){
      bitset<9> BIT(state);      
      int bitmask = (1<<c)-1;
      int bits_L  = __builtin_popcount(state & bitmask);
      int bits_R  = __builtin_popcount(state) - bits_L;
      cout << "(" << c << "," << r  << ") : " << BIT << endl;
      cout << "bits ( " << bits_L << "," << bits_R << ")" << endl;
      if( bits_L   > len[r]   ) continue; 
      if( bits_L+C-c < len[r] ) continue;
      if( c+bits_R < len[r+1] ) continue; 
      cout << "here" << endl;

      int next_state = state & (~(1<<c));
      dp[next_phase][next_state] = max(dp[next_phase][next_state],
				       dp[phase][state]);
      answer = max(answer,dp[next_phase][next_state]);

      next_state |= (1<<c);
      if( bits_L == len[r] ){
	dp[next_phase][next_state] = max(dp[next_phase][next_state],
					 dp[phase][state]);
	continue;
      }

      int score = 0;
      char char_M = s[r][c];
      if( bits_L > 0 && c-1 > 0 && ((state>>(c-1))&1) ){
	char char_L = s[r][bits_L-1];
	if( char_M == char_L ) score++;
      }

      if( bits_R > 0 && r+1 < R && ((state>>c)&1) ){
	char char_B = s[r+1][len[r+1]-bits_R];
	if( char_M == char_B ) score++;
      }

      dp[next_phase][next_state] = max(dp[next_phase][next_state],
				       dp[phase][state] + score);
      cout << "score = " << score << endl;
      BIT = next_state;
      cout << "dp[" << next_phase << "][" << BIT << "] = " << dp[next_phase][next_state] << endl;
      answer = max(answer,dp[next_phase][next_state]);
    }
  }
  cout << 2 * answer << endl;
  */

  /*

  rep(r,R)rep(c,C)rep(state,(1<<C)){

    int bitmask = (1<<c)-1;
    int bits_L = __builtin_popcount(bitmask&state);
    int bits_R = __builtin_popcount(state)-bits_L;

    if( bits_L > len[r]   ) continue;

    int next_state = state & ~(1<<c);
    int next_r = r, next_c = c+1;
    if( next_c >= C ) next_r++, next_c = 0;
    dp[next_r][next_c][next_state] = max(dp[next_r][next_c][next_state],dp[r][c][state]);
    answer = max(answer,dp[next_r][next_c][next_state]);

    char char_M = s[r][bits_L];
    int score = 0;
    if( c-1>=0 && ((state>>(c-1))&1) ){
      if(bits_L-1>=0){
	char char_L = s[r][bits_L-1];
	if( char_M == char_L ) score++;
      }
    }

    if( (state>>c)&1 && r+1 < R){
      char char_B = s[r+1][len[r+1]-bits_R];
      if( char_M == char_B ) score++;
    }

    next_state |= (1<<c);
    dp[next_r][next_c][next_state] = max(dp[next_r][next_c][next_state],dp[r][c][state]+score);
    answer = max(answer,dp[next_r][next_c][next_state]);

  }

  cout << 2*answer << endl;

  */

  /*
  REP(r,1,R){
    rep(c,C){
      rep(state,(1<<C)){
	int bitmask = (1<<(c+1))-1;
	int bits_R = __builtin_popcount(bitmask&state);
	int bits_L = __builtin_popcount(state)-bits_R;

	if( bits_R > len[r-1] ) continue;
	if( bits_L > len[r] ) continue;

	int next_state = state & ~(1<<c);
	int prer = ((c-1>=0)?r  :r-1);
	int prec = ((c-1>=0)?c-1:C-1);
	dp[r][c][next_state] = max(dp[r][c][next_state],dp[prer][prec][state]);
	answer = max(answer,dp[r][c][next_state]);

	if( bits_L+1 > len[r] ) continue;

	next_state |= (1<<c);
	char char_M = s[r][len[r]-bits_L-1];
	int score = 1;
	if( (state>>c) & 1 ){
	  char char_T = s[r-1][bits_R];
	  if( char_M == char_T ) score++;
	}

	if( ( (state>>(c+1)) & 1 ) ) {
	  char char_L = s[r][len[r]-bits_L];
	  if( char_M == char_L )score++;
	}
	if( score == 1 ) continue;
	dp[r][c][next_state] = max(dp[r][c][next_state],dp[prer][prec][state]+score);
	answer = max(answer,dp[r][c][next_state]);
      }
    }
  }

  cout << answer << endl;
  */

  return 0;
}

/*
21:27 -  22:26 give up 
the following code is too slow!



#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<climits>
#include<bitset>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

int dx[] = {0,-1};
int dy[] = {-1,0};
string G[130];
int dp[130][(1<<17)];
string line[2];

int main(){
  int H,W;
  cin >> H >> W;
  vector<int> loop[H];
  rep(i,H){
    cin >> G[i];
    int remain = W - (int)G[i].size();
    //cout << i << " => " << remain << endl;
    rep(j,(1<<W)){
      if(__builtin_popcount(j) == remain)loop[i].push_back(j);
    } 
  }

  vector<string> pre[H];
  rep(i,H){
    sort(loop[i].begin(),loop[i].end());
    loop[i].erase(unique(loop[i].begin(),loop[i].end()),loop[i].end());
    cout << loop[i].size() << endl;
    assert((int)loop[i].size() < (1<<W));
    rep(j,loop[i].size()){
      int state = loop[i][j],idx = 0;
      string line = "";
      rep(j,W){
	if((state>>j) & 1)line += " ";
	else              line += G[i][idx++];
      }
      pre[i].push_back(line);
    }
  }
  //cout << "-----------" << endl;
  int ans = 0;
  rep(y,H){
    rep(i,loop[y].size()){
      int state = loop[y][i];
      line[1] = pre[y][i];
      rep(j,((y-1>=0)?loop[y-1].size():1) ){
	int pstate = ((y-1>=0)?loop[y-1][j]:0);
	line[0] = ((y-1>=0)?pre[y-1][j]:string(W,' '));
	int point = 0;
	rep(k,W){
	  int X = k, Y = 1;
	  rep(l,2){
	    int nx = X + dx[l], ny = Y + dy[l];
	    if(!( 0 <= nx && nx < W && 0 <= ny && ny < H ))continue;
	    if(line[Y][X] != ' ' && line[Y][X] == line[ny][nx]) point++;
	  }
	}
	dp[y][state] = max(dp[y][state],((y-1>=0)?dp[y-1][pstate]:0)+point);
	ans = max(ans,dp[y][state]);
      } 
    }
  }
  cout << ans * 2 << endl;
  return 0;
}

*/