#include <bits/stdc++.h>
using namespace std;
int n, k, m;
struct TRIE {
  int cnt, deep;
  int son[10];
  void init() {
    cnt = 0;
    memset(son, -1, sizeof son);
  }
} a[510];
int pos;
char s[510];
int tot;
void insert() {
  scanf("%s%d", s, &tot);
  int now = 0;
  for (int i = 0, len = strlen(s); i < len; ++i) {
    int to = s[i] - '0';
    if (a[now].son[to] == -1) {
      a[now].son[to] = ++pos;
      a[pos].init();
      a[pos].deep = a[now].deep + 1;
    }
    now = a[now].son[to];
  }
  a[now].cnt += tot;
}
int dp[510][15][510];
int dp2[510][15][510][15];
int DFS(int x, int rem, int fa) {
  if (dp[x][rem][fa] != -1) return dp[x][rem][fa];
  dp[x][rem][fa] = 0x3f3f3f3f;
  if (rem) dp[x][rem][fa] = DFS(x, rem - 1, x);
  vector<int> G;
  for (int i = 0; i < 10; ++i)
    if (a[x].son[i] != -1) G.push_back(a[x].son[i]);
  dp2[x][rem][fa][G.size()] = 0;
  for (int i = (int)G.size() - 1; i >= 0; --i) {
    for (int j = 0; j <= rem; ++j)
      dp2[x][rem][fa][i] = min(dp2[x][rem][fa][i],
                               dp2[x][rem - j][fa][i + 1] + DFS(G[i], j, fa));
  }
  dp[x][rem][fa] = min(
      dp[x][rem][fa], dp2[x][rem][fa][0] + a[x].cnt * (a[x].deep - a[fa].deep));
  return dp[x][rem][fa];
}
void init() {
  a[0].init();
  pos = 0;
  a[0].deep = 0;
}
int main() {
  while (scanf("%d%d", &n, &k) != EOF) {
    init();
    for (int i = 1; i <= n; ++i) insert();
    memset(dp, -1, sizeof dp);
    memset(dp2, 0x3f, sizeof dp2);
    printf("%d\n", DFS(0, k, 0));
  }
  return 0;
}
