#include <bits/stdc++.h>
using namespace std;
bool home = 1;
signed realMain();
signed main() {
  home = 0;
  if (home) {
    freopen("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0);
    cin.tie(0);
  }
  realMain();
}
long long n, k, y;
struct node {
  long long pay, id;
  node* k[10];
  node() {
    id = 0;
    pay = 0;
    for (long long j = 0; j < 10; j++) {
      k[j] = 0;
    }
  }
};
node* root = new node;
const long long N = 500 + 7;
const long long K = 12;
const long long INF = (long long)1e18;
long long dp[N][N][K];
long long nw[N][K];
string s;
void dfs(node* now, long long h) {
  long long id = now->id;
  for (long long dif = 0; dif < h; dif++) {
    for (long long cnt = 0; cnt < K; cnt++) {
      dp[id][dif][cnt] = now->pay * dif;
    }
  }
  for (long long digit = 0; digit <= 9; digit++) {
    if (!now->k[digit]) {
      continue;
    }
    s += (char)(digit + '0');
    dfs(now->k[digit], h + 1);
    s.pop_back();
    long long id_k = now->k[digit]->id;
    for (long long dif = 0; dif < h; dif++) {
      for (long long cnt = 0; cnt < K; cnt++) {
        nw[dif][cnt] = INF;
        for (long long from = 0; from <= cnt; from++) {
          nw[dif][cnt] = min(nw[dif][cnt],
                             dp[id][dif][cnt - from] + dp[id_k][dif + 1][from]);
        }
      }
    }
    for (long long dif = 0; dif < h; dif++) {
      for (long long cnt = 0; cnt < K; cnt++) {
        dp[id][dif][cnt] = nw[dif][cnt];
      }
    }
  }
  for (long long dif = 1; dif < h; dif++) {
    for (long long cnt = 1; cnt < K; cnt++) {
      dp[id][dif][cnt] = min(dp[id][dif][cnt], dp[id][0][cnt - 1]);
    }
  }
}
signed realMain() {
  for (long long i = 0; i < N; i++) {
    for (long long j = 0; j < N; j++) {
      for (long long k = 0; k < K; k++) {
        dp[i][j][k] = INF;
      }
    }
  }
  cin >> n >> k;
  root->id = ++y;
  for (long long i = 1; i <= n; i++) {
    string s;
    long long cost;
    cin >> s >> cost;
    node* now = root;
    for (auto& ch : s) {
      long long digit = ch - '0';
      if (!now->k[digit]) {
        now->k[digit] = new node;
        now->k[digit]->id = ++y;
      }
      now = now->k[digit];
    }
    now->pay += cost;
  }
  dfs(root, 1);
  cout << dp[1][0][k] << "\n";
  return 0;
}
