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.