В первый класс школы в Нлогонии набрали \(n\) учеников. Директор хочет разделить их в два класса, каждый ученик должен оказаться ровно в одном из этих классов. Если в один класс попадут два школьника, имена которых начинаются с одной и той же буквы, то они будут слишком много болтать друг с другом (ведь наверняка у них много общего). Обозначим за \(x\) количество таких пар учеников в некотором разбиении на два класса. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми и учитываются один раз.
Например, если всего в классе \(6\) учеников — «olivia», «jacob», «tanya», «jack», «oliver» и «jessica», то:
- разделение на два класса («jack», «jacob», «jessica», «tanya») и («olivia», «oliver») даст \(x=4\) (\(3\) пары будут болтать в первом классе, \(1\) пара будет болтать во втором классе),
- разделение на два класса («jack», «tanya», «olivia») и («jessica», «oliver», «jacob») даст \(x=1\) (\(0\) пар будут болтать в первом классе, \(1\) пара будет болтать во втором классе).
Вам дан список из \(n\) имен. Какое минимальное значение \(x\) мы можем получить, распределив этих школьников на два класса?
Обратите внимание, не запрещается распределять всех учеников в один и тот же класс, оставив другой пустым.
Выходные данные
Выведите одно целое число \(x\) — минимально возможное количество пар учеников, которые будут болтать друг с другом.
Примечание
В первом примере минимально возможное число пар равно \(1\). Такого можно добиться, например, распределив всех кроме jose в один класс, а jose — в другой, так что болтать будут только jorge и jerry.
Во втором примере минимально возможное число пар равно \(2\). Такого можно добиться, например, распределив kambei, gorobei, shichiroji и kyuzo в один класс, а heihachi, katsushiro и kikuchiyo в другой. В этом случае болтать будут kambei с kyuzo, а также katsushiro с kikuchiyo.
В третьем примере минимально возможное число пар равно \(4\). Этого можно добиться, распределив трех школьников с именем mike в один класс, а остальных двух — в другой. Тогда в одном классе будет три болтающих пары, а в другом — одна.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
jorge
jose
oscar
jerry
|
1
|
|
2
|
7
kambei
gorobei
shichiroji
kyuzo
heihachi
katsushiro
kikuchiyo
|
2
|
|
3
|
5
mike
mike
mike
mike
mike
|
4
|