#include <bits/stdc++.h>
const int N = 505, inf = 0x3f3f3f3f, K = 15;
int n, k, idx;
int nxt[N][10], cnt[N];
int dp[N][N][K];
void insert(const std::string& s, int t) {
  int now = 0;
  for (char ch : s) {
    if (!nxt[now][ch - '0']) nxt[now][ch - '0'] = ++idx;
    now = nxt[now][ch - '0'];
  }
  cnt[now] += t;
}
int tmp[N][K][2][K];
int dfs(int x, int up, int k) {
  if (~dp[x][up][k]) return dp[x][up][k];
  dp[x][up][k] = inf;
  if (k > 0) dp[x][up][k] = dfs(x, 0, k - 1);
  int* tmp[2] = {::tmp[x][k][0], ::tmp[x][k][1]};
  std::memset(tmp[0], 0x3f, sizeof ::tmp[0][0][0]);
  std::memset(tmp[1], 0x3f, sizeof ::tmp[0][0][0]);
  tmp[0][0] = 0;
  int now = 0, lst = 1;
  for (int i = 0; i < 10; ++i)
    if (nxt[x][i]) {
      std::swap(now, lst);
      std::memset(tmp[now], 0x3f, sizeof ::tmp[0][0][0]);
      for (int j = 0; j <= k; ++j)
        for (int l = j; l <= k; ++l)
          tmp[now][l] = std::min(tmp[now][l],
                                 tmp[lst][j] + dfs(nxt[x][i], up + 1, l - j));
    }
  dp[x][up][k] = std::min(dp[x][up][k], tmp[now][k] + up * cnt[x]);
  return dp[x][up][k];
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    std::string s;
    int t;
    std::cin >> s >> t;
    insert(s, t);
  }
  std::memset(dp, -1, sizeof dp);
  std::cout << dfs(0, 0, k) << '\n';
  return 0;
}
