Вам надано ~N~ рядків ~S_1 ​ , S_2 ​ ,…, S_N ~.

Знайдіть мінімальну довжину рядка, який містить усі ці рядки як підрядки.

Тут рядок ~S~ містить рядок ~T~ як підрядок, якщо ~T~ можна отримати шляхом видалення нуля або більше символів з початку та нуля або більше символів з кінця ~S~.

Обмеження

• ~N~ є цілим числом.
• ~1≤N≤20~
• ~S_i~ ​ — це рядок, що складається з малих англійських літер, довжина яких дорівнює принаймні 1.
• Загальна довжина ~S_1 ​,S_2 ​,…,S_N~ ​ становить не більше ~2×10^5 ~.

Формат вхідних даних

Перший рядок містить ціле число ~N~.

Наступні  ~N~ рядків містять ~S_i~.

Формат вихідних даних

У вихідний потік виведіть відповідь - одне ціле число.

Приклад вхідних даних

3
snuke
kensho
uk

Приклад вихідних даних

9

Рядок snukensho довжиною 9 містить усі ~S_1 ​, S_2~ ​ і ~S_3~ ​ як підрядки.

Зокрема, символи з першого по пʼятий snukensho відповідають ~S_1~ ​, з четвертого по девʼятий – ~S_2~ ​, а з третього по четвертий – ~S_3~ ​.

Жоден коротший рядок не містить усі ~S_1 ​, S_2~ ​ і ~S_3~ ​ як підрядки. Отже, відповідь 9.

Приклад вхідних даних

3
abc
abc
arc

Приклад вихідних даних

6

Приклад вхідних даних

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

Приклад вихідних даних

27