快速拨号

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Polycarp 的电话簿中有 $n$ 个电话号码。第 $i$ 个号码由只含数字的字符串 $s_i$ 表示，他每天需要拨打这个号码 $m_i$ 次。

新手机有 $k$ 个快速拨号键。每个快速拨号键可以事先绑定一个数字串，这个数字串不一定恰好是电话簿中的号码。输入一个号码时，可以先按一个快速拨号键，再用普通数字键输入剩余后缀；也可以完全使用普通数字键。快速拨号键只能在尚未输入任何数字时使用，绑定后不能更改。

在最优绑定和最优输入方式下，求每天拨完电话簿中所有号码所需按普通数字键的最少总次数。按快速拨号键本身不计入答案。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，每行包含一个数字串 $s_i$ 和一个整数 $m_i$。

输出格式

输出一个整数，表示最少需要按普通数字键的次数。

样例输入 1

3 1
0001 5
001 4
01 1

样例输出 1

14

样例输入 2

3 1
0001 5
001 6
01 1

样例输出 2

18

数据范围

$1\le n\le500$，$1\le k\le10$，$1\le m_i\le500$，$s_i$ 非空且只含字符 0 至 9，所有 $s_i$ 的长度之和不超过 $500$。