Alice have strings named to . Each string has a length . Now she wants to type them on the txt-editor (Sequence not required).

For each string , she has two choice.

The first choice is to type all characters of one by one (this will cost ).

The second choice is to choose one string , which Alice has typed before , then paste it into a single line (this will cost ) . Now we call this string , Alice can perform the following operation any time to get .

- Delete any character from , each character costs .

- Insert any character anywhere in , each character costs .

Such as we want to get from , we will do the following operations :

1. Paste into a new line , cost .

2. Delete the character in to get , cost .

3. Insert before the first character of to get , cost .

4. Insert after the second character of to get , cost .

Totally cost .

Now Alice wants to type all the strings , please help her to find the minimum cost .

The first line contains two integer  .

The next  lines , each line contains an integer , and a string  with length  , Separates by a space . 

 only has lowercase letters .

Print an integer  --- the minimum cost  .

2 1
4 baba
4 abaa

7

In this sample , Alice can type the second string  first , cost  , then copy this string , cost  , cost  to get  from  (->->) . The total cost is  .