You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

AB子串

题目描述

Snuke 有 $N$ 个字符串。 第 $i$ 个字符串是 $s_i$。

在以某种顺序排列它们之后，让我们将这些字符串连接成一个字符串。 在结果字符串中找到 AB 的最大可能出现次数。

输入格式

第一行一个整数 $N$ ，接下来 $N$ 行每行一个字符串 $s_i$ 。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

3
ABCA
XBAZ
BAD

样例输出 #1

2

样例 #2

样例输入 #2

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

样例输出 #2

4

样例 #3

样例输入 #3

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

样例输出 #3

4

数据范围

• $1\ \leq\ N\ \leq\ 10^{4}$
• $2\ \leq\ |s_i|\ \leq\ 10$
• $s_i$ 只包含大写英文字母

样例解释 1

- 将ABCA, BAD, XBAZ 拼成 ABCABADXBAZ ，AB 出现 $2$ 次。