CF1082F.Speed Dial

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?

波利卡普的电话簿中包含 $n$ 个电话号码，每个号码由 $s_i$（号码本身）和 $m_i$（波利卡普每天拨打该号码的次数）描述。

波利卡普刚刚购买了一部全新手机，该手机具备一项令人惊叹的快速拨号功能！具体而言，手机上有 $k$ 个按键可以被分配一个号码（该号码不一定要来自电话簿）。要输入某个号码，波利卡普可以先按这 $k$ 个按键中的某一个，然后使用普通数字键完成剩余部分（当然，也可以完全不使用快速拨号键，而仅用数字键输入整个号码）。

快速拨号键只能在尚未输入任何数字时使用。任意按键一旦分配了号码，便不可重新分配。

在为快速拨号键分配号码，并以最优方式对电话簿中的每个号码各拨打 $m_i$ 次的前提下，波利卡普所能达到的数字键总按压次数的最小值是多少？

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$.

第一行包含两个整数 $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$。

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.

输出一个整数——即 Polycarp 在为快捷拨号按钮分配号码，并以最优方式依次拨打电话簿中的每个号码（按给定次数）后，所能达到的数字按键总次数的最小值。

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.

第一个示例中唯一的快速拨号按钮上应显示“0001”。数字按键的总按压次数为：第一个号码 $0 \cdot 5$ 次 + 第二个号码 $3 \cdot 4$ 次 + 第三个号码 $2 \cdot 1$ 次，总计 $14$ 次。

第二个示例中唯一的快速拨号按钮上应显示“00”。数字按键的总按压次数为：第一个号码 $2 \cdot 5$ 次 + 第二个号码 $1 \cdot 6$ 次 + 第三个号码 $2 \cdot 1$ 次，总计 $18$ 次。