← 返回题目列表

Codeforces · 1082/F

F. 快速拨号

中文机器翻译题面 查看原题

Polycarp 的电话簿包含 $$$n$$$ 个电话号码,每个电话号码均由 $$$s_i$$$ 描述 - 号码本身和 $$$m_i$$$ - Polycarp 每天拨打该号码的次数。

Polycarp 刚刚购买了一部全新手机,具有令人惊叹的快速拨号功能!更准确地说,它上面的 $$$k$$$ 按钮可以分配一个号码(不需要从电话簿中获取)。要输入某个数字,Polycarp 可以按这些 $$$k$$$ 按钮之一,然后使用常用的数字按钮完成数字(也可以仅使用数字按钮输入数字)。

快速拨号按钮只能在未输入数字时使用。任何按钮都不能重新分配其编号。

Polycarp 将号码分配给快速拨号按钮并以最佳方式输入电话簿中的每个号码给定的次数后,可以实现的最小总按数字次数是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le 10$$$) — Polycarp 电话簿中的号码数量以及他的新手机的快速拨号按钮数量。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含字符串 $$$s_i$$$ 和整数 $$$m_i$$$ $$$(1 \le m_i \le 500)$$$,其中 $$$s_i$$$ 是从 $$$0$$$ 到 $$$9$$$ 的非空数字字符串(包含$$$i$$$ 个号码),$$$m_i$$$ 分别是拨打的次数。

保证所有电话号码的总长度不超过$$$500$$$。

输出

打印一个整数——Polycarp 将号码分配给快速拨号按钮并以最佳方式输入电话簿中的每个号码指定次数后可以实现的最小总位数。

示例

输入 #1

3 1
0001 5
001 4
01 1

输出 #1

14

输入 #2

3 1
0001 5
001 6
01 1

输出 #2

18

注意

第一个示例中唯一的快速拨号按钮应带有“0001”。按数字按钮的总数为:第一个数字 $$$0 \cdot 5$$$ + 第二个数字 $$$3 \cdot 4$$$ + 第三个数字 $$$2 \cdot 1$$$。总共$$$14$$$。

第二个示例中唯一的快速拨号按钮应带有“00”。按数字按钮的总数为:第一个数字 $$$2 \cdot 5$$$ + 第二个数字 $$$1 \cdot 6$$$ + 第三个数字 $$$2 \cdot 1$$$。总共$$$18$$$。