#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma G++ optimize("O2")
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
using namespace std;
const int N = 555;
const int M = 22222;
const int MOD = 1e9 + 7;
const int intINF = 1e9;
const long long llINF = 2e18;
const double pi = acos(-1.0);
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
unsigned long long readull() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
char s[N];
int t[N][10], dp[N][N][12], a[N], n, K, cnt;
void predo() {}
void init() {
  n = read(), K = read();
  cnt = 1;
  for (int i = (int)1; i <= (int)n; i++) {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    int u = 1;
    for (int j = (int)1; j <= (int)len; j++) {
      int c = s[j] - '0';
      if (!t[u][c]) t[u][c] = ++cnt;
      u = t[u][c];
    }
    a[u] += read();
  }
}
void dfs(int u) {
  for (int c = (int)0; c <= (int)9; c++) {
    int v = t[u][c];
    if (!v) continue;
    dfs(v);
  }
  for (int i = (int)0; i <= (int)cnt; i++)
    for (int j = (int)0; j <= (int)K; j++) dp[u][i][j] = i * a[u];
  for (int c = (int)0; c <= (int)9; c++) {
    int v = t[u][c];
    if (!v) continue;
    for (int i = (int)0; i <= (int)cnt; i++) {
      for (int j = (int)K; j >= (int)0; j--) {
        dp[u][i][j] += dp[v][i + 1][0];
        for (int k = (int)1; k <= (int)j; k++) {
          dp[u][i][j] = min(dp[u][i][j], dp[u][i][j - k] + dp[v][i + 1][k]);
          dp[u][i][j] = min(dp[u][i][j], dp[u][i][j - k] + dp[v][0][k - 1]);
        }
      }
    }
  }
}
void solve() {
  dfs(1);
  printf("%d\n", dp[1][0][K]);
}
int main() {
  predo();
  int cas = 1;
  while (cas--) {
    init();
    solve();
  }
  return 0;
}
