Вам даны \(n\) слов одинаковой длины \(m\), состоящие из строчных букв латинского алфавита, \(i\)-е слово обозначается \(s_i\).
За один ход вы можете выбрать любую позицию в любом отдельном слове и заменить букву в этой позиции на предыдущую или следующую букву в алфавитном порядке. Например:
- вы можете заменить 'e' на 'd' или на 'f';
- 'a' может быть заменена только на 'b';
- 'z' может быть заменена только на 'y'.
Разница между двумя словами — это минимальное число ходов, необходимое для того, чтобы сделать их равными. Например, разница между «best» и «cost» составляет \(1 + 10 + 0 + 0 = 11\).
Найдите минимальную разницу между \(s_i\) и \(s_j\) такую, что \((i < j)\). Другими словами, найдите минимальную разницу по всем возможным парам из \(n\) слов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную разница среди всех возможных пар заданных строк.
Примечание
Для второго набора входных данных можно показать, что наилучшей парой является («abb», «bef»), которая имеет разницу, равную \(8\), что можно получить следующим образом: заменить первый символ первой строки на 'b' за один ход, заменить второй символ второй строки на 'b' за \(3\) хода и заменить третий символ второй строки на 'b' за \(4\) хода, что в сумме дает \(1 + 3 + 4 = 8\) ходов.
В третьем наборе существует только одна возможная пара, и можно показать, что минимальное количество ходов, необходимое для того, чтобы строки стали равными, равно \(35\).
В четвертом наборе есть пара строк, которые уже равны, поэтому ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 4
best
cost
6 3
abb
zba
bef
cdu
ooo
zzz
2 7
aaabbbc
bbaezfe
3 2
ab
ab
ab
2 8
aaaaaaaa
zzzzzzzz
3 1
a
u
y
|
11
8
35
0
200
4
|