#P1. [Sleeping Cup #1] Sleeping pairs

[Sleeping Cup #1] Sleeping pairs

注意

本题需要使用文件读写(pairs.in / pairs.out)。

题目背景

小 C 是一间卧铺车厢的管理员。这间车厢内有若干张床,每张床都分上下铺(即每张床可以睡 22 个人)。这天,正当它满载着乘客行驶时,车厢里突然停电了!

这立刻激起了乘客们的愤怒。他们要求小 C 妥善处理这个问题,把他们转移到另一间车厢。同时,有些人借此向小 C 抱怨,他们的上铺(或下铺)睡觉时打呼噜,使得他们无法入睡。

题目描述

小 C 向你总结了他所需要解决的问题:

  • 车厢内共有 nn 张床,每张床都分上下铺,相当于一张 nn22 列的表格
  • 每张床位上都有一位乘客。有的乘客会打呼噜(用 Z 表示),有的乘客不会(用 X 表示)。也就是说,每个格子中都有一个字符 ZX
  • 乘客们希望同一张床中上下铺乘客的属性(即是否打呼噜)相同,即要求每行 22 个格子中的字符相同
  • 小 C 可以做以下操作,每操作一次(每次只能选择下面一项进行操作)花费 11 点体力
    • 交换两个相邻的乘客(相邻两床的上铺,相邻两床的下铺,或者同一床的上下铺),即交换 22 个相邻格子中的字符
    • 移走一张上下铺安排符合乘客预期的床,即删除表格中符合要求的一行
  • 现要求移走所有的床(即删空表格,保证可以实现),问最少需要多少点体力。

输入格式

第一行一个正整数 nn

下面 nn 行,每行 22 个字符,形成一个 nn22 列的表格。

输出格式

一行一个正整数,表示答案。

样例

3
XZ
ZZ
ZX
4
18
XX
XX
XX
XX
XZ
ZX
XZ
ZZ
XZ
XZ
ZZ
XZ
ZX
XZ
XX
XX
XX
XX
24

提示

样例 11 解释:

一种最优的操作方案是:删除第 22 行,交换第 11 列(或第 22 列)剩下的的 22 个字符,再分别删除剩下的 22 行,一共花费 44 点体力。


对于 100%100\% 的数据,1n1051 \le n \le 10^5,且 XZ 均有偶数个(保证可以达成目标)。