#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
constexpr auto MOD = 1000000007LL;
constexpr auto LINF = (1LL << 60);
constexpr auto INF = 2147483647LL;
constexpr auto PI = 3.1415926535897932384626433;
constexpr auto EPS = 1E-9;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> p) {
  out << p.first << ' ' << p.second;
  return out;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &v) {
  for (auto &x : v) in >> x;
  return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> v) {
  for (int i = 0; i < v.size(); i++)
    out << v[i] << (i + 1 == v.size() ? '\n' : ' ');
  out.flush();
  return out;
}
int dp[501][12][501];
int tmp[12][501];
int nxt[501][11], w[501], h[501];
int n, k, nodecnt = 1;
void insert(string str, int num) {
  int now = 0;
  for (auto x : str) {
    if (nxt[now][x - '0'] == 0) {
      nxt[now][x - '0'] = nodecnt++;
    }
    now = nxt[now][x - '0'];
  }
  w[now] += num;
}
void dpfs(int now) {
  for (int i = 0; i < 10; i++) {
    if (nxt[now][i]) {
      h[nxt[now][i]] = h[now] + 1;
      dpfs(nxt[now][i]);
    }
  }
  for (int kk = k; kk >= 0; kk--) {
    for (int hh = h[now]; hh >= 0; hh--) {
      dp[now][kk][hh] = MOD;
    }
  }
  for (int hh = h[now]; hh >= 0; hh--) {
    dp[now][(hh == h[now])][hh] = w[now] * (h[now] - hh);
  }
  for (int i = 0; i < 10; i++) {
    int x = nxt[now][i];
    if (x == 0) continue;
    for (int kk = 0; kk <= k; kk++)
      for (int hh = 0; hh <= h[now]; hh++) tmp[kk][hh] = MOD;
    for (int myk = k; myk >= 0; myk--) {
      for (int hisk = k - myk; hisk >= 0; hisk--) {
        for (int hh = h[now]; hh >= 0; hh--) {
          tmp[myk + hisk][hh] =
              min(tmp[myk + hisk][hh], dp[now][myk][hh] + dp[x][hisk][hh]);
          tmp[myk + hisk][hh] =
              min(tmp[myk + hisk][hh], dp[now][myk][hh] + dp[x][hisk][h[x]]);
        }
      }
    }
    for (int kk = k; kk >= 0; kk--) {
      for (int hh = h[now]; hh >= 0; hh--) {
        dp[now][kk][hh] = tmp[kk][hh];
      }
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k;
  ++k;
  string str;
  int num;
  for (int i = 0; i < n; i++) {
    cin >> str >> num;
    insert(str, num);
  }
  dpfs(0);
  int res = INF;
  for (int i = 0; i <= k; i++) {
    res = min(dp[0][i][h[0]], res);
  }
  cout << res << endl;
  return 0;
}
