#include <bits/stdc++.h>
using namespace std;
int n, tms;
void upd(int &x, int y) { x = min(x, y); }
struct trietree {
  int node[505][12];
  int sum[505];
  int dp[505][505][12];
  int dp2[505][505][12][12];
  bool vis[505][505][15];
  int dep[505];
  int tot;
  void insert(char ch[], int val) {
    int now = 0;
    int l = strlen(ch);
    for (int i = 0; i < l; i++) {
      int rt = ch[i] - '0';
      if (node[now][rt] == 0) node[now][rt] = ++tot, dep[tot] = dep[now] + 1;
      now = node[now][rt];
    }
    sum[now] += val;
  }
  void dfs(int x, int p, int lft) {
    if (vis[x][p][lft]) return;
    vis[x][p][lft] = 1;
    if (lft > 0) dfs(x, x, lft - 1), upd(dp[x][p][lft], dp[x][x][lft - 1]);
    vector<int> ch;
    for (int i = 0; i < 10; i++)
      if (node[x][i]) ch.push_back(node[x][i]);
    dp2[x][p][lft][ch.size()] = 0;
    for (int i = ch.size() - 1; i >= 0; i--) {
      int t = ch[i];
      for (int j = 0; j <= lft; j++) {
        dfs(t, p, j);
        upd(dp2[x][p][lft][i], dp2[x][p][lft - j][i + 1] + dp[t][p][j]);
      }
    }
    upd(dp[x][p][lft], dp2[x][p][lft][0] + (dep[x] - dep[p]) * sum[x]);
  }
  int solve() {
    memset(dp, 0x3f, sizeof(dp));
    memset(dp2, 0x3f, sizeof(dp2));
    dfs(0, 0, tms);
    return dp[0][0][tms];
  }
} trie;
char buf[1008];
int main() {
  cin >> n >> tms;
  for (int i = 0; i < n; i++) {
    scanf("%s", buf);
    int gg;
    cin >> gg;
    trie.insert(buf, gg);
  }
  cout << trie.solve();
  return 0;
}
