#include <bits/stdc++.h>
using namespace std;
const int mxn = 502, w = 10;
int n, m = 1, k;
int a[mxn], b[mxn], d[mxn], first[mxn], sz[mxn];
int tr[mxn][w], dp[mxn][mxn], dp2[mxn][mxn];
void dfs2(int c) {
  sz[c] = 1, dp2[c][0] = dp2[c][1] = a[c];
  for (int i = 0, x; i < w; i++)
    if (x = tr[c][i]) {
      d[x] = d[c] + 1;
      dfs2(x);
      memcpy(first, dp2[c], (sz[c] + 1) * sizeof(int));
      memset(dp2[c], 0x3f, (sz[c] + sz[x] + 1) * sizeof(int));
      for (int j = 0; j <= sz[c]; j++)
        for (int l = 0; l <= sz[x]; l++) {
          dp2[c][j + l] = min(dp2[c][j + l], first[j] + dp2[x][l]);
        }
      sz[c] += sz[x];
    }
  for (int i = 1; i <= sz[c]; i++) {
    dp2[c][i] = min(dp2[c][i], dp[c][i - 1] - a[c] * d[c]);
  }
}
void dfs(int c) {
  for (int i = 0, x; i < w; i++)
    if (x = tr[c][i]) dfs(x);
  d[c] = 0;
  memset(dp[c], 0x3f, sizeof(dp[c]));
  dfs2(c);
  memcpy(dp[c], dp2[c], sizeof(dp[c]));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    int x, c = 0;
    string second;
    cin >> second >> x;
    for (char &j : second) {
      j -= '0';
      ;
      if (!tr[c][j]) tr[c][j] = m++;
      a[c = tr[c][j]] += x;
    }
  }
  dfs(0);
  cout << dp[0][k] << '\n';
  return 0;
}
