#include <bits/stdc++.h>
using namespace std;
const int MN = 555;
int N, K;
string S[MN];
int R[MN];
int trie[MN][10], sz[MN], tcnt;
int dp[MN][MN][11], dep[MN], tmp[MN][11];
void mrg(int u, int v) {
  for (int i = 0; i <= dep[u]; i++)
    for (int j = 0; j <= K; j++) tmp[i][j] = 0;
  for (int i = 0; i <= dep[u]; i++) {
    for (int j = 0; j <= K; j++) {
      for (int k = K; k >= j; k--) {
        tmp[i][k] = max(tmp[i][k], dp[u][i][k - j] + dp[v][i][j]);
        if (j) {
          tmp[i][k] = max(tmp[i][k], dp[u][i][k - j] + dp[v][dep[v]][j - 1] +
                                         (dep[v] - i) * sz[v]);
        }
      }
    }
  }
  for (int i = 0; i <= dep[u]; i++)
    for (int j = 0; j <= K; j++) dp[u][i][j] = tmp[i][j];
}
void dfs(int u) {
  for (int i = 0; i < 10; i++) {
    int v = trie[u][i];
    if (!v) continue;
    dep[v] = dep[u] + 1;
    dfs(v);
    mrg(u, v);
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> N >> K;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    cin >> S[i] >> R[i];
    ans += (int)S[i].size() * R[i];
  }
  tcnt = 1;
  for (int i = 0; i < N; i++) {
    int u = 0;
    sz[u] += R[i];
    for (int j = 0; j < S[i].size(); j++) {
      if (!trie[u][S[i][j] - '0']) {
        trie[u][S[i][j] - '0'] = tcnt++;
      }
      u = trie[u][S[i][j] - '0'];
      sz[u] += R[i];
    }
  }
  dfs(0);
  cout << ans - dp[0][0][K];
}
