#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(int x) {
  write(x);
  puts("");
}
const int N = 505, INF = 1e9;
int len, dp[N][15][N], g[N][15][N][15], sum[N], n, K, tran[N][26], tot, dep[N];
char s[N];
inline void insert() {
  int x = 0;
  for (int i = 1; i <= len; i++) {
    int c = s[i] - '0';
    if (!tran[x][c]) tran[x][c] = ++tot, dep[tot] = dep[x] + 1;
    x = tran[x][c];
  }
  sum[x] += read();
}
inline void init() {
  n = read();
  K = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    len = strlen(s + 1);
    insert();
  }
}
inline void upd(int &x, int y) { x = min(x, y); }
int dfs(int x, int lim, int fa) {
  if (~dp[x][lim][fa]) return dp[x][lim][fa];
  int &ans = dp[x][lim][fa];
  ans = INF;
  if (lim) upd(ans, dfs(x, lim - 1, x));
  int q[10], cnt = 0;
  for (int i = 0; i < 10; i++) {
    if (tran[x][i]) q[cnt++] = tran[x][i];
  }
  g[x][lim][fa][cnt] = 0;
  for (int i = cnt - 1; i >= 0; i--) {
    for (int j = 0; j <= lim; j++) {
      upd(g[x][lim][fa][i], dfs(q[i], j, fa) + g[x][lim - j][fa][i + 1]);
    }
  }
  upd(ans, g[x][lim][fa][0] + sum[x] * (dep[x] - dep[fa]));
  return ans;
}
inline void solve() {
  memset(dp, -1, sizeof dp);
  memset(g, 127 / 3, sizeof g);
  writeln(dfs(0, K, 0));
}
int main() {
  init();
  solve();
  return 0;
}
