C - AB Substrings 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

すぬけ君は N 個の文字列を持っています。i 番目の文字列は s_i です。

これらの文字列を好きな順序で並べたあと、連結して 1 つの文字列を作ることを考えます。 作った文字列に AB という部分文字列が含まれる個数としてありうる値のうち、最大値を求めてください。

制約

  • 1 \leq N \leq 10^{4}
  • 2 \leq |s_i| \leq 10
  • s_i は英大文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

N
s_1
\vdots
s_N

出力

答えを出力せよ。

入力例 1

3
ABCA
XBAZ
BAD

出力例 1

2
  • 例えば、ABCA, BAD, XBAZ の順で連結して ABCABADXBAZ を作ったとき、AB という部分文字列は 2 つ含まれます。

入力例 2

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

出力例 2

4

入力例 3

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

出力例 3

4

Score : 400 points

Problem Statement

Snuke has N strings. The i-th string is s_i.

Let us concatenate these strings into one string after arranging them in some order. Find the maximum possible number of occurrences of AB in the resulting string.

Constraints

  • 1 \leq N \leq 10^{4}
  • 2 \leq |s_i| \leq 10
  • s_i consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:

N
s_1
\vdots
s_N

Output

Print the answer.

Sample Input 1

3
ABCA
XBAZ
BAD

Sample Output 1

2

For example, if we concatenate ABCA, BAD and XBAZ in this order, the resulting string ABCABADXBAZ has two occurrences of AB.

Sample Input 2

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

Sample Output 2

4

Sample Input 3

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

Sample Output 3

4