#include <bits/stdc++.h>
using namespace std;
int a[5005];
struct node {
  node *next[10];
  int v;
} mem[5005 * 50], *null, *tot;
struct TRIE {
  node *root;
  node *newnode() {
    node *p = ++tot;
    *p = *null;
    return p;
  }
  void init() {
    null = tot = mem;
    for (int i = 0; i < 10; i++) null->next[i] = null;
    null->v = 0;
    root = newnode();
  }
  void insert(char *s, int val) {
    node *p = root;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) {
      int v = s[i] - '0';
      if (p->next[v] == null) p->next[v] = newnode();
      p = p->next[v];
    }
    p->v += val;
  }
} trie;
int n, k, f[511][511][12], vis[511][511];
char s[5005];
int F1[12], F2[12];
void dfs(int xx, int j) {
  if (vis[xx][j]) return;
  vis[xx][j] = 1;
  node *x = mem + xx;
  for (int i = 0; i < 10; i++) {
    node *y = x->next[i];
    if (y == null) continue;
    int yy = y - mem;
    dfs(yy, j + 1);
    dfs(yy, 1);
  }
  for (int i = 0; i <= 11; i++) F1[i] = 0;
  for (int i = 0; i <= 11; i++) F2[i] = 0;
  for (int i = 0; i < 10; i++) {
    node *y = x->next[i];
    if (y == null) continue;
    int yy = y - mem;
    for (int k1 = 10; k1 >= 0; k1--) {
      F1[k1] += f[yy][j + 1][0];
      for (int k2 = 1; k2 <= k1; k2++)
        F1[k1] = min(F1[k1], F1[k1 - k2] + f[yy][j + 1][k2]);
    }
    for (int k1 = 10; k1 >= 0; k1--) {
      F2[k1] += f[yy][1][0];
      for (int k2 = 1; k2 <= k1; k2++)
        F2[k1] = min(F2[k1], F2[k1 - k2] + f[yy][1][k2]);
    }
  }
  for (int k = 0; k <= 11; k++) {
    f[xx][j][k] = min(xx == 1 ? 2e9 : F1[k] + x->v * j, k ? F2[k - 1] : 2e9);
  }
}
int main() {
  trie.init();
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int val;
    scanf("%s%d", s + 1, &val);
    a[i] = val;
    trie.insert(s, val);
  }
  dfs(1, 1);
  printf("%d\n", f[1][1][k + 1]);
}
