#include <bits/stdc++.h>
const int MAX_S = 500;
const int MAX_K = 10;
int n, m, k;
char s[MAX_S + 1];
struct data {
  int cnt, dif;
};
bool operator<(data lhs, data rhs) {
  if (lhs.cnt != rhs.cnt)
    return lhs.cnt < rhs.cnt;
  else
    return lhs.dif > rhs.dif;
}
void refine(std::vector<data> &tar, std::vector<data> &src) {
  tar.clear();
  std::sort(src.begin(), src.end());
  int max = -1;
  for (data dat : src)
    if (dat.dif > max) {
      max = dat.dif;
      tar.push_back(dat);
    }
}
struct node {
  int cnt;
  std::vector<data> vec[MAX_K + 1];
  node *ptr[10];
  node() : cnt(), vec() {
    for (int i = 0; i < 10; ++i) ptr[i] = nullptr;
  }
  void add(char *s, int m) {
    cnt += m;
    if (*s) {
      if (ptr[*s - '0'] == nullptr) ptr[*s - '0'] = new node();
      ptr[*s - '0']->add(s + 1, m);
    }
  }
  void solve() {
    for (int i = 0; i <= MAX_K; ++i) vec[i].push_back({0, 0});
    for (node *p : ptr)
      if (p != nullptr) {
        p->solve();
        std::vector<data> tmp[MAX_K + 1];
        for (int i = 0; i <= MAX_K; ++i)
          for (int j = 0; i + j <= MAX_K; ++j)
            for (data u : vec[i])
              for (data v : p->vec[j])
                tmp[i + j].push_back({u.cnt + v.cnt, u.dif + v.dif});
        for (int i = 0; i <= MAX_K; ++i) refine(vec[i], tmp[i]);
      }
    if (cnt == 0) return;
    std::vector<data> tmp[MAX_K + 1];
    for (int i = 0; i <= MAX_K; ++i)
      for (data dat : vec[i]) {
        tmp[i].push_back({dat.cnt + cnt - dat.dif, dat.dif});
        if (i < MAX_K) tmp[i + 1].push_back({dat.cnt, cnt});
      }
    for (int i = 0; i <= MAX_K; ++i) refine(vec[i], tmp[i]);
  }
} root;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%s%d", s, &m);
    root.add(s, m);
  }
  root.cnt = 0;
  root.solve();
  printf("%d\n", root.vec[k].front().cnt);
  return 0;
}
