Chomiki

Limit pamięci: 64 MB

Bajtazar prowadzi hodowlę chomików. Każdy chomik ma unikalne imię, złożone z małych liter alfabetu angielskiego. Chomiki mają obszerną i komfortową klatkę. Bajtazar chce umieścić pod klatką wyświetlacz, który będzie wyświetlał imiona jego chomików. Wyświetlacz będzie miał postać ciągu liter, z których każda może być zapalona lub zgaszona. Naraz będzie wyświetlane tylko jedno imię chomika. Zapalone litery tworzące to imię muszą znajdować się obok siebie.

Bajtazar chce, aby wyświetlacz mógł wyświetlać imiona chomików przynajmniej w różnych miejscach. Dopuszcza on, aby to samo imię mogło być wyświetlane w kilku różnych miejscach, i nie wymaga, aby każde imię mogło być wyświetlane na wyświetlaczu. Zauważ, że wystąpienia imion na wyświetlaczu mogą dowolnie na siebie nachodzić. Możesz założyć, że imię żadnego z chomików nie występuje (jako spójny fragment) w imieniu żadnego innego chomika. Bajtazar poprosił Cię o pomoc w wyznaczeniu najmniejszej liczby liter, z jakich musi składać się wyświetlacz.

Inaczej mówiąc, należy wyznaczyć minimalną długość napisu (złożonego z małych liter alfabetu angielskiego), w którym łączna liczba wystąpień imion chomików będzie nie mniejsza niż . (Mówimy, że słowo występuje w napisie , jeżeli stanowi spójny fragment ).

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające, odpowiednio, liczbę chomików Bajtazara i minimalną liczbę wystąpień imion chomików na wyświetlaczu. Każdy z kolejnych wierszy zawiera niepusty napis złożony z małych liter alfabetu angielskiego będący imieniem chomika. Sumaryczna długość wszystkich imion nie przekracza liter.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - minimalną liczbę liter, z których musi być zbudowany wyświetlacz.

Przykład

Dla danych wejściowych:

4 5
monika
tomek
szymon
bernard

poprawną odpowiedzią jest:

23

Najkrótszy wyświetlacz może mieć, na przykład, postać: szymonikatomekszymonika. Zawiera on łącznie 5 wystąpień imion chomików: szymon i monika występują dwukrotnie, tomek raz, a bernard ani razu.

Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.