CF1082F Speed Dial

Polycarp神犇的电话册里有$n$个电话号码，每一个号码都被描述为$s_i$，即号码本身，以及$m_i$​，就是Polycarp神犇每天拨打这个电话的次数。 Polycarp刚刚购买了一个手机，拥有极其优秀的快速拨号的功能！（这很惊人吗？）准确的说，这个手机上有$k$个按钮可以绑定一个号码（不一定是电话册里的）。为了输入一个号码，Polycarp神犇可以先按$k$个按钮中的一个，然后再用数字按钮完成这个号码（输入的一个号码只用数字键打出也是可能的）。 快速拨号键只可以在没有输入任何数字时使用，且其数字不可以被重新绑定。 那么Polycarp神犇在ta已经向快拨键赋值后将号码簿里的所有号码拨他应该拨的次数（即$m_i$​）后，他最少要按多少次数字键？

第一行是两个整数$n$，$k$。（$1 \leq n \leq 500, 1\leq k\leq 10$）含义见上。 对于接下来的$n$行，第$i$行包含一个字符串$s_i$，和一个整数$m_i$。（$1 \leq m_i \leq 500$，$s_i$是一个仅包含字符‘0’至‘9’的字符串）含义见上。 你可以认为所有$s_i$的长度总和$\leq 500$。

输出单个整数，即“Polycarp神犇在ta已经向快拨键赋值后将号码簿里的所有号码拨他应该拨的次数（即$m_i$​）后，他最少要按数字键的次数”。

--- 样例一： 唯一的快拨按钮应有“0001”与之绑定。总数为14。 --- 样例二： 唯一的快拨按钮应有“00”与之绑定。总数为18。