题目描述

您可能知道，越南河粉（pho）是河内最常见的菜肴之一。它包含一种特殊的米粉、肉（通常是牛肉或鸡肉）和葱，浸在美味的汤中。越南人早餐、午餐、晚餐甚至便餐都喜欢吃河粉。对于游客来说，尤其是在河内寒冷的天气里，品尝河粉是必做之事。

你在越南经营一家有 $n$ 张餐桌（编号为 $1$ 到 $n$）的 phở bò（牛肉河粉）餐厅。2024 年 ICPC 亚洲及太平洋锦标赛的参赛者们正在您的餐厅里。每位参赛者最初都坐在某张餐桌旁，且每张餐桌最初都至少有一位参赛者。每位参赛者想点两种最著名的河粉之一：phở tái（半熟牛肉河粉）或 phở chín（全熟牛肉河粉）。餐桌 $i$ 的初始状态由二进制字符串 $S_i$ 表示。$S_i$ 的长度是最初坐在该桌的参赛者人数。如果最初坐在该桌的第 $j$ 位参赛者想点 phở tái，则 $S_i$ 的第 $j$ 个字符为 $0$；如果想点 phở chín，则为 $1$。

为了便于记录订单，餐厅希望坐在同一桌的参赛者点同样的菜。也就是说，对于每张餐桌，以下至少有一条必须成立：

• 所有坐在该桌的参赛者都想点 phở tái。
• 所有坐在该桌的参赛者都想点 phở chín。

为了满足此要求以及参赛者的订单，您需要将零名或多名参赛者移动到其他餐桌。目标餐桌必须是这 $n$ 张餐桌之一。换句话说，您不能增加新的餐桌。每张餐桌可容纳的参赛者数量没有限制。移动参赛者后，每张餐桌都应满足以下条件：要么该餐桌没有参赛者，要么所有坐在该餐桌的参赛者都点同样的菜。

由于移动参赛者需要时间，您希望计算出需要移动的参赛者的最少人数。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 100,000$)。

接下来的 $n$ 行，每行包含一个二进制字符串。第 $i$ 行包含 $S_i$ ($1 \le |S_i| \le 200,000$)。

所有 $i$ 的 $|S_i|$ 的总和不超过 $500,000$。

输出格式

输出一个整数，代表您需要移动的参赛者的最少人数。

4
11101101
00
10001
10

5

2
101010
010101

6

5
0000
11
0
00000000
1

0

提示

样例解释 #1

你可以移动

• 最初坐在 1 号桌的第七位参赛者到 3 号桌，
• 最初坐在 1 号桌的第四位参赛者到 4 号桌，
• 最初坐在 3 号桌的第一和第五位参赛者到 1 号桌，以及
• 最初坐在 4 号桌的第一位参赛者到 1 号桌。

这样一来，所有坐在 1 号桌的参赛者点的都是 phở chín，而坐在其他桌的参赛者点的都是 phở tái。可以证明，无法在移动少于 5 名参赛者的情况下满足要求。