#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXNUMBER = 500;
const int MAXBUT = 10;
const int MAXSUMLEN = 500;
const int MAXTNODE = MAXSUMLEN + 1;
struct TNode {
  int nxt[10], freq;
};
int nnumber, nbut;
char s[MAXNUMBER][MAXSUMLEN + 1];
int freq[MAXNUMBER];
TNode t[MAXTNODE];
int nt, troot;
int tmake() {
  assert(nt < MAXTNODE);
  int ret = nt++;
  memset(t[ret].nxt, -1, sizeof(t[ret].nxt));
  t[ret].freq = 0;
  return ret;
}
int dp[MAXTNODE][MAXTNODE + 1][MAXBUT + 1];
void upd(int &a, int b) { a = min(a, b); }
void dfs(int at, int dep) {
  for (int x = (0); x < (10); ++x)
    if (t[at].nxt[x] != -1) dfs(t[at].nxt[x], dep + 1);
  for (int j = (0); j <= (dep); ++j)
    for (int k = (0); k <= (nbut); ++k) dp[at][j][k] = j * t[at].freq;
  for (int x = (0); x < (10); ++x)
    if (t[at].nxt[x] != -1) {
      int to = t[at].nxt[x];
      for (int j = (0); j <= (dep); ++j)
        for (int k = nbut; k >= 0; --k) {
          for (int dk = (1); dk <= (nbut - k); ++dk)
            upd(dp[at][j][k + dk], dp[at][j][k] + dp[to][j + 1][dk]);
          dp[at][j][k] += dp[to][j + 1][0];
        }
    }
  for (int j = (0); j <= (dep); ++j)
    for (int k = (1); k <= (nbut); ++k) upd(dp[at][j][k], dp[at][0][k - 1]);
}
int solve() {
  nt = 0;
  troot = tmake();
  for (int i = (0); i < (nnumber); ++i) {
    int at = troot, len = strlen(s[i]);
    for (int j = (0); j < (len); ++j) {
      int x = s[i][j] - '0';
      if (t[at].nxt[x] == -1) t[at].nxt[x] = tmake();
      at = t[at].nxt[x];
    }
    t[at].freq += freq[i];
  }
  dfs(troot, 0);
  return dp[troot][0][nbut];
}
void run() {
  scanf("%d%d", &nnumber, &nbut);
  for (int i = (0); i < (nnumber); ++i) scanf("%s%d", s[i], &freq[i]);
  printf("%d\n", solve());
}
int main() {
  run();
  return 0;
}
