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。

题目描述

Polycarp's phone book contains $ n $ phone numbers, each of them is described by $ s_i $ — the number itself and $ m_i $ — the number of times Polycarp dials it in daily. Polycarp has just bought a brand new phone with an amazing speed dial feature! More precisely, $ k $ buttons on it can have a number assigned to it (not necessary from the phone book). To enter some number Polycarp can press one of these $ k $ buttons and then finish the number using usual digit buttons (entering a number with only digit buttons is also possible). Speed dial button can only be used when no digits are entered. No button can have its number reassigned. What is the minimal total number of digit number presses Polycarp can achieve after he assigns numbers to speed dial buttons and enters each of the numbers from his phone book the given number of times in an optimal way?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 500 $ , $ 1 \le k \le 10 $ ) — the amount of numbers in Polycarp's phone book and the number of speed dial buttons his new phone has. The $ i $ -th of the next $ n $ lines contain a string $ s_i $ and an integer $ m_i $ $ (1 \le m_i \le 500) $ , where $ s_i $ is a non-empty string of digits from $ 0 $ to $ 9 $ inclusive (the $ i $ -th number), and $ m_i $ is the amount of times it will be dialed, respectively. It is guaranteed that the total length of all phone numbers will not exceed $ 500 $ .

输出格式

Print a single integer — the minimal total number of digit number presses Polycarp can achieve after he assigns numbers to speed dial buttons and enters each of the numbers from his phone book the given number of times in an optimal way.

输入输出样例

输入样例 #1

3 1
0001 5
001 4
01 1

输出样例 #1

14

输入样例 #2

3 1
0001 5
001 6
01 1

输出样例 #2

18

说明

The only speed dial button in the first example should have "0001" on it. The total number of digit button presses will be $ 0 \cdot 5 $ for the first number + $ 3 \cdot 4 $ for the second + $ 2 \cdot 1 $ for the third. $ 14 $ in total. The only speed dial button in the second example should have "00" on it. The total number of digit button presses will be $ 2 \cdot 5 $ for the first number + $ 1 \cdot 6 $ for the second + $ 2 \cdot 1 $ for the third. $ 18 $ in total.