Начинающий волшебник Вася на экзамене должен показать знание заклинаний. Он не совсем надеется на свою память и решил по опыту поколений сделать себе кольца и выгравировать на них \(N\) самых трудных заклинаний.

Гравировка каждой буквы — процесс долгий и дорогой, поэтому Вася хочет использовать пересечение начал и окончаний некоторых заклинаний.

Помогите Васе минимизировать количество букв для гравировки. Известно, что ни одно из заклинаний не является полной подстрокой другого. Гравировать можно на нескольких кольцах, но при этом каждое из заклинаний должно полностью находиться хотя бы на одном из колец и читаться по часовой стрелке. На кольце гравировка идёт в один ряд.