题目描述

hsq 打字速度很快！所以老师想请他帮个忙，输入一些单词到电脑里。

现在总共有 $n$ 个单词需要 hsq 来输入，第 $i$ 个单词的长度为 $len_i$

对于每个单词， hsq 有两种选择：

1. 直接把这个单词打出来，花费时间为 $len_i$
2. 从之前打印过的单词中选一个，将它复制过来，然后进行添加、删除，复制粘贴需要花费时间为 $k$，每次添加、删除一个字母需要花费的时间均为 $1$

现在 hsq 想知道自己输入完这些单词的最少需要花费多少时间？

P.S. 老师并不要求单词输入的顺序，只要所有单词最后都被输入到电脑中即可

输入格式

第一行 $2$ 个整数 $n,$ $k$, 分别表示单词的数量和复制粘贴的代价 。

接下来 $n$ 行，首先是一个数字 $len_i$ ，表示每个单词的长度，然后是一个字符串表示第 $i$ 个单词

输出格式

一个整数，表示最小的总代价

数据范围

对于 $40\%$ 数据满足： $1 \leq n \leq 18$

对于 $100\%$ 数据满足： $1 \leq n,k,len_i \leq 100$

特别的保证：单词都是由小写字母构成

样例输入

5 2
9 bcabbbcca
7 cbcbaaa
8 cbcaaaca
8 aaccabbb
8 ccbbbcca

样例输出

33