#include <bits/stdc++.h>
#pragma GCC target("pclmul")
using ul = std::uint32_t;
using ull = std::uint64_t;
using li = std::int32_t;
using ll = std::int64_t;
using llf = long double;
using uss = std::uint8_t;
ul n;
ul k;
const ul maxk = 10;
const ul maxlen = 500;
ul to[maxlen + 2][10];
ul len[maxlen + 2];
ul m[maxlen + 2];
ul ans[maxlen + 2][maxlen + 1][maxk + 1];
ul tmp[maxk + 1];
ul sz[maxlen + 2];
ul tim;
char str[maxlen + 2];
int main() {
  std::scanf("%u%u", &n, &k);
  tim = 1;
  ul out = 0;
  for (ul it = 1; it <= n; ++it) {
    std::scanf("%s", str + 1);
    ul curr = 1;
    for (ul i = 1; str[i]; ++i) {
      if (!to[curr][str[i] - '0']) {
        ++tim;
        to[curr][str[i] - '0'] = tim;
        len[tim] = len[curr] + 1;
      }
      curr = to[curr][str[i] - '0'];
    }
    ul tmp;
    std::scanf("%u", &tmp);
    m[curr] += tmp;
    out += tmp * len[curr];
  }
  for (ul curr = tim; curr >= 1; --curr) {
    for (ul up = 0; up <= len[curr]; ++up) {
      sz[curr] = 0;
      for (ul c = 0; c <= 9; ++c) {
        if (!to[curr][c]) {
          continue;
        }
        ul next = to[curr][c];
        std::memcpy(tmp, ans[curr][up],
                    sizeof(ul) * (std::min(k, sz[curr]) + 1));
        std::memset(ans[curr][up], 0, sizeof(ul) * (std::min(k, sz[curr]) + 1));
        for (ul a = std::min(k, sz[curr]); ~a; --a) {
          for (ul b = std::min(k - a, sz[next]); ~b; --b) {
            ans[curr][up][a + b] =
                std::max(ans[curr][up][a + b], tmp[a] + ans[next][up][b]);
          }
        }
        sz[curr] += sz[next];
      }
    }
    ++sz[curr];
    for (ul c = 0; c <= 9; ++c) {
      if (to[curr][c]) {
        m[curr] += m[to[curr][c]];
      }
    }
    for (ul up = 0; up <= len[curr]; ++up) {
      for (ul a = std::min(k, sz[curr]); a >= 1; --a) {
        ans[curr][up][a] =
            std::max(ans[curr][up][a],
                     ans[curr][len[curr]][a - 1] + (len[curr] - up) * m[curr]);
      }
    }
  }
  ul outm = 0;
  for (ul i = 0; i <= std::min(k, sz[1]); ++i) {
    outm = std::max(outm, ans[1][0][i]);
  }
  std::printf("%u\n", out - outm);
  return 0;
}
