. Now she wants to type them on the txt-editor ., which Alice has typed before , then paste it into a single line (this will cost. S , Alice can perform the following operation any time to get. Now Alice wants to type all the strings , please help her to find the minimum cost .
Alice have n n strings named S_1 S 1 to S_n S n . Each string has a length l_i l i . Now she wants to type them on the txt-editor (Sequence not required). For each string S_i S i , she has two choice. The first choice is to type all characters of S_i S i one by one (this will cost l_i l i ). The second choice is to choose one string S_j S j , which Alice has typed before , then paste it into a single line (this will cost k k) . Now we call this string S S , Alice can perform the following operation any time to get S_i S i . - Delete any character from S S , each character costs 1 1 . - Insert any character anywhere in S S , each character costs 1 1 . Such as we want to get abac abac from bdc bdc , we will do the following operations : 1. Paste bdc bdc into a new line , cost k k . 2. Delete the 2nd 2nd character d d in bdc bdc to get bc bc , cost 1 1 . 3. Insert a a before the first character of bc bc to get abc abc , cost 1 1 . 4. Insert a a after the second character of abc abc to get abac abac , cost 1 1 . Totally cost k+3 k+3 . Now Alice wants to type all the strings , please help her to find the minimum cost .
