#include <bits/stdc++.h>
using namespace std;
const int N = 507, K = 11, inf = 1e9;
struct node {
  int nxt[10];
  int cnt;
  node() {
    memset(nxt, -1, sizeof(nxt));
    cnt = 0;
  }
} trie[N];
int cnt;
int h[N];
int n, k;
int dp[N][K][N];
int dp2[N][K][N][K];
void add(string s, int m) {
  int cur = 0;
  for (int i = 0; i < s.size(); i++) {
    int x = s[i] - '0';
    if (trie[cur].nxt[x] == -1) {
      trie[cnt] = node();
      trie[cur].nxt[x] = cnt;
      h[cnt] = h[cur] + 1;
      cnt++;
    }
    cur = trie[cur].nxt[x];
  }
  trie[cur].cnt += m;
}
int work(int x, int k, int fa) {
  if (dp[x][k][fa] != -1) return dp[x][k][fa];
  vector<int> son;
  for (int i = 0; i <= 9; i++)
    if (trie[x].nxt[i] != -1) son.push_back(trie[x].nxt[i]);
  dp[x][k][fa] = inf;
  if (k > 0) dp[x][k][fa] = work(x, k - 1, x);
  dp2[x][k][fa][0] = 0;
  for (int i = 1; i <= son.size(); i++) {
    dp2[x][k][fa][i] = inf;
    for (int j = 0; j <= k; j++)
      dp2[x][k][fa][i] = min(
          dp2[x][k][fa][i], work(son[i - 1], j, fa) + dp2[x][k - j][fa][i - 1]);
  }
  dp[x][k][fa] = min(dp[x][k][fa],
                     dp2[x][k][fa][son.size()] + (h[x] - h[fa]) * trie[x].cnt);
  return dp[x][k][fa];
}
int main() {
  trie[0] = node();
  cnt = 1;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    string s;
    int m;
    cin >> s >> m;
    add(s, m);
  }
  memset(dp, -1, sizeof(dp));
  printf("%d", work(0, k, 0));
  return 0;
}
