#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
namespace solver {
int n, k;
int nxt[500 + 10][10];
int cnt[500 + 10], tot = 1;
int dp[510][11][510], dp2[510][11][510][11];
void ins(string str, int val) {
  int p = 1;
  for (int i = 0; i < str.size(); i++) {
    if (nxt[p][str[i] - '0'] == 0) nxt[p][str[i] - '0'] = ++tot;
    p = nxt[p][str[i] - '0'];
  }
  cnt[p] += val;
}
int dfs(int now, int rest, int len) {
  if (~dp[now][rest][len]) {
    return dp[now][rest][len];
  }
  int res = 1e9;
  if (rest >= 1) {
    res = dfs(now, rest - 1, 0);
  }
  for (int i = 0; i <= rest; i++) {
    dp2[now][i][len][10] = 0;
  }
  for (int j = 9; j >= 0; j--) {
    int v = nxt[now][j];
    if (v == 0) {
      for (int i = 0; i <= rest; i++) {
        dp2[now][i][len][j] = dp2[now][i][len][j + 1];
      }
      continue;
    }
    for (int i = rest; i >= 0; i--) {
      dp2[now][rest][len][j] =
          min(dp2[now][rest][len][j],
              dp2[now][rest - i][len][j + 1] + dfs(v, i, len + 1));
    }
  }
  res = min(res, dp2[now][rest][len][0] + len * cnt[now]);
  dp[now][rest][len] = res;
  return res;
}
void solve() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    string str;
    int val;
    cin >> str >> val;
    ins(str, val);
  }
  memset(dp2, 0x3f, sizeof dp2);
  memset(dp, -1, sizeof dp);
  cout << dfs(1, k, 0);
}
};  // namespace solver
int main() {
  solver::solve();
  return 0;
}
