Sanhai的文件分类Ultra

题目背景

CSP2025 S组的比赛数据在解压时发生异常，四道题目的测试文件全部散落在一个网格窗口中。Sanhai的文件夹是按照名称排序的，他必须使用鼠标圈选矩形区域来分类文件。分类过程中文件位置会不断重排，Sanhai需要最快分类文件以尽快上传到OJ上

任务描述

Sanhai需要完成以下操作：

1. 为每道题目创建同名文件夹
2. 将属于该题目的所有文件移入对应文件夹
3. 必须在完整处理完一道题的所有文件后，才能开始处理下一题
4. 分类必须是正确的
5. 打开文件夹算一次操作，把文件移除文件夹也算一次操作

鼠标圈选操作必须满足：

• 圈选的矩形区域大于$1×1$（至少包含$1$个单元格）

输入格式

第一行包含两个整数$n$和$m$，表示网格的行数和列数$2\le n,m \le 10^5$

接下来$n$行，每行$m$个字符串，描述网格初始状态：

• 文件名格式为：XYY.Z（$X$为$A-D$的大写字母，$YY$为$01-10$的两位编号，Z为"in"或"out"）
• 空单元格用"."表示
• 文件名保证合法，且属于$A$、$B$、$C$、$D$四道题目之一
• 每个测试点有.in和.out两个文件 areyouok

输出格式

一个整数，表示完成所有文件分类所需的最小鼠标圈选操作次数

样例

样例输入1

4 7
B01.in B01.out B02.in B02.out A01.in A01.out A02.in
A02.out C01.in C01.out C02.in C02.out D01.in D01.out
D02.in D02.out . . . . .
. . . . . . .

样例输出1

4

样例输入2

4 7
A01.in A01.out A02.in A02.out B01.in B01.out B02.in
B02.out C01.in C01.out C02.in C02.out D01.in D01.out
D02.in D02.out 

样例输出2

5

样例输入3

4 7
A01.in A01.out A02.in A02.out A03.in A03.out B01.in
B01.out B02.in B02.out B03.in B03.out C01.in C01.out
C02.in C02.out C03.in C03.out D01.in D01.out D02.in
D02.out D03.in D03.out 

样例输出3

7

样例解释

样例1解释

• 网格大小：4×7
• 每道题有2个文件（1个测试点）
• 文件位置随操作动态变化：
  1. 创建文件夹"A"后，A题文件集中出现 → $1$次圈选
  2. 创建文件夹"B"后，B题文件集中出现 → $1$次圈选
  3. 创建文件夹"C"后，C题文件集中出现 → $1$次圈选
  4. 创建文件夹"D"后，D题文件集中出现 → $1$次圈选
• 总圈选次数：$4$次

样例2解释

• 网格大小：$4×7$
• 每道题有$4$个文件（$2$个测试点）
• 关键变化：
  1. 前三道题文件集中 → 各需$1$次圈选
  2. 处理最后一道题时，文件被分割成两部分：
     • 第一部分：$3$个文件 → $1$次圈选
     • 第二部分：$1$个文件+空位 → 需额外$1$次圈选
• 总圈选次数：$3+2=5$次

样例3解释

• 网格大小：$4×7$
• 每道题有6个文件（3个测试点）
• 文件被严重分割：
  1. 题A文件分$2$次圈选
  2. 题B文件分$1$次圈选
  3. 题C文件分$2$次圈选
  4. 题D文件分$2$次圈选
• 总圈选次数：$2+1+2+2=7$次

数据范围

• $30\%$数据：$n×m \le 10^2$
• $60\%$数据：$n×m \le 20^2$
• $100\%$数据：$2 \le n,m \le 10^5$