2021 China Shaanxi Provincial
4
Problem C
Type the strings
Alice have n strings named S
1
to S
n
. Each string has a length l
i
. Now she wants to type
them on the txt-editor (Sequence not required).
For each string S
i
, she has two choice.
The first choice is to type all characters of S
i
one by one (this will cost l
i
).
The second choice is to choose one string S
j
, which Alice has typed before , then paste it into
a single line (this will cost k) . Now we call this string S , Alice can perform the following
operation any time to get S
i
.
- Delete any character from S , each character costs 1 .
- Insert any character anywhere in S , each character costs 1 .
Such as we want to get abac from bdc , we will do the following operations :
1. Paste bdc into a new line , cost k .
2. Delete the 2nd character d in bdc to get bc , cost 1 .
3. Insert a before the first character of bc to get abc , cost 1 .
4. Insert a after the second character of abc to get abac , cost 1 .
Totally cost k+3 .
Now Alice wants to type all the strings , please help her to find the minimum cost .
Input
The first line contains two integer n (1≤n≤10
2
),k (1≤k≤10
2
) .
The next n lines , each line contains an integer l
i
(1≤l
i
≤10
2
), and a string S
i
with length l
i
,
Separates by a space .
S
i
only has lowercase letters .
Output
Print an integer — the minimum cost .
Sample Input Sample Output
评论0