#include <bits/stdc++.h>
using namespace std;
int n, k, m[505];
string s[505];
int tot = 0;
struct trie {
  int ct, num;
  trie* ch[10];
  trie* par;
  trie(int nn) {
    ct = 0;
    num = nn;
    for (int i = 0; i <= 9; ++i) ch[i] = NULL;
    par = NULL;
  }
};
void ins(trie* cur, string val, int amt, int ps = 0) {
  if (ps == val.size()) {
    cur->ct += amt;
    return;
  }
  int go = val[ps] - '0';
  if (cur->ch[go] == NULL) {
    cur->ch[go] = new trie(++tot);
    cur->ch[go]->par = cur;
  }
  ins(cur->ch[go], val, amt, ps + 1);
}
int dp[505][12][12][505];
bool done[505][12][12][505];
const int inf = 1e9;
int solve(trie* cur, int k, int fwhich, int cht, int ht) {
  if (!cur) return 0;
  int v = cur->num;
  if (done[v][k][fwhich][ht]) return dp[v][k][fwhich][ht];
  int& ret = dp[v][k][fwhich][ht];
  done[v][k][fwhich][ht] = 1;
  ret = inf;
  if (fwhich == 0) {
    ret = min(ret, solve(cur, k, fwhich + 1, cht, ht) +
                       (int)(cur->ct) * (int)(cht - ht));
    if (k > 0) ret = min(ret, solve(cur, k - 1, fwhich + 1, cht, cht));
    return ret;
  }
  if (fwhich == 10) {
    ret = solve(cur->ch[fwhich - 1], k, 0, cht + 1, ht);
    return ret;
  }
  for (int ass = 0; ass <= k; ++ass) {
    ret = min(ret, solve(cur, k - ass, fwhich + 1, cht, ht) +
                       solve(cur->ch[fwhich - 1], ass, 0, cht + 1, ht));
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  trie* root = new trie(++tot);
  for (int i = 1; i <= n; ++i) {
    cin >> s[i] >> m[i];
    ins(root, s[i], m[i]);
  }
  assert(tot <= 503);
  cout << solve(root, k, 0, 1, 1) << '\n';
}
