#include <bits/stdc++.h>
const int INF = 2000000005;
const long long BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const long double PI = 3.141592653589793238462643;
const double eps = 1e-9;
using namespace std;
vector<pair<int, int> > dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool valid(int x, int y, int n, int m) {
  return x >= 0 && y >= 0 && x < n && y < m;
}
mt19937 rng(1999999973);
int o = 0;
struct node {
  int sons, h, sum, ind, col;
  unordered_map<char, node*> g;
  node(int H) {
    sons = 0, h = H, sum = 0, col = 0;
    ind = o, o++;
  }
};
const int N = 505, K = 11;
int n, k, m[N], dp[N][N][K];
string s[N];
node* root = new node(0);
inline void add(int i) {
  node* v = root;
  for (int j = 0; j < s[i].length(); j++) {
    if (v->g.find(s[i][j]) == v->g.end()) {
      v->g[s[i][j]] = new node(j + 1);
    }
    v = v->g[s[i][j]];
  }
  v->sum += v->h * m[i];
  v->sons += m[i];
  v->col += m[i];
}
void pre_calc(node* v) {
  for (auto i = v->g.begin(); i != v->g.end(); i++) {
    pre_calc(i->second);
    v->sons += i->second->sons;
    v->sum += i->second->sum;
  }
}
void dfs(node* v, int last, int rem) {
  if (rem < 0) return;
  int cur = v->ind;
  if (dp[cur][last][rem] != INF) return;
  if (rem == 0) {
    dp[cur][last][rem] = v->sum - last * v->sons;
    return;
  }
  vector<int> curmin(11), prevmin(11);
  vector<int> sons;
  sons.reserve(v->g.size());
  for (auto i = v->g.begin(); i != v->g.end(); i++) {
    for (int j = 0; j <= rem; j++) {
      dfs(i->second, last, j);
      dfs(i->second, v->h, j - 1);
    }
    sons.push_back(i->second->ind);
  }
  if (sons.empty()) {
    if (rem == 0)
      dp[cur][last][rem] = v->sum - last * v->col;
    else
      dp[cur][last][rem] = 0;
    return;
  }
  for (int i = 0; i < 11; i++) {
    curmin[i] = 0;
  }
  for (int i = sons.size() - 1; i >= 1; i--) {
    prevmin = curmin;
    for (int j = rem; j >= 0; j--) {
      curmin[j] = INF;
      for (int gv = j; gv >= 0; gv--) {
        curmin[j] = min(curmin[j], dp[sons[i]][last][gv] + prevmin[j - gv]);
      }
    }
  }
  for (int j = 0; j <= rem; j++) {
    dp[cur][last][rem] =
        min(dp[cur][last][rem], v->col * v->h - v->col * last +
                                    dp[sons[0]][last][j] + curmin[rem - j]);
  }
  for (int i = 0; i < 11; i++) {
    prevmin[i] = curmin[i] = 0;
  }
  rem--;
  for (int i = sons.size() - 1; i >= 1; i--) {
    prevmin = curmin;
    for (int j = rem; j >= 0; j--) {
      curmin[j] = INF;
      for (int gv = j; gv >= 0; gv--) {
        curmin[j] = min(curmin[j], dp[sons[i]][v->h][gv] + prevmin[j - gv]);
      }
    }
  }
  for (int j = 0; j <= rem; j++) {
    dp[cur][last][rem + 1] =
        min(dp[cur][last][rem + 1], dp[sons[0]][v->h][j] + curmin[rem - j]);
  }
}
void define_dp() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int kk = 0; kk < K; kk++) {
        dp[i][j][kk] = INF;
      }
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> s[i] >> m[i];
    add(i);
  }
  define_dp();
  pre_calc(root);
  dfs(root, 0, k);
  cout << dp[0][0][k];
  return 0;
}
