P13622 [ICPC 2024 APC] Pho Restaurant

您可能知道，越南河粉（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$。

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

**样例解释 #1** 你可以移动 * 最初坐在 1 号桌的第七位参赛者到 3 号桌， * 最初坐在 1 号桌的第四位参赛者到 4 号桌， * 最初坐在 3 号桌的第一和第五位参赛者到 1 号桌，以及 * 最初坐在 4 号桌的第一位参赛者到 1 号桌。 这样一来，所有坐在 1 号桌的参赛者点的都是 *phở chín*，而坐在其他桌的参赛者点的都是 *phở tái*。可以证明，无法在移动少于 5 名参赛者的情况下满足要求。