// while (true) keepingTraining();
#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vs             vector <string>
#define vi             vector <int>
#define dqi            deque<int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define debug(...)     __f (#__VA_ARGS__, __VA_ARGS__)
#define FOR(i, a, b)   for (int i = (a); i < (b); i++)
#define F0R(i, a)      for (int i = 0; i < (a); i++)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a, x, y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

template <typename T, typename... Args>
void ccout(const T& arg, const Args &...args) {
  std::cout << arg;
  ((std::cout << " " << args), ...);
  std::cout << endl;
}

void ccin() {}

template <typename T, typename... Args>
void ccin(T& arg, Args &...args) {
  std::cin >> arg;
  ccin(args...);
}

template<typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template<typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args &&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}

#define fastIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void readWriteIO() {
  // This def is only in judges, so we can use in our code without problems
#ifndef ONLINE_JUDGE
  freopen("./input.txt", "r", stdin);
  freopen("./output.txt", "w", stdout);
#endif
  fastIO();
}

bool compare(const pair<string, int> a, pair<string, int> b) {
  return a.S < b.S;
}

void solve() {
  int n, k; ccin(n, k);
  vector<vi> v(26, vi(26, INT_MAX));
  F0R(i, n) {
    string s; int c; ccin(s, c);
    v[s[0] - 'a'][s[1] - 'a'] = c;
  }

  // for (auto x : v) {
  //   print(x);
  // }

  vi dp(26, 0);
  if (k % 2) {
    for (int i = 1; i < k; i += 2) {
      vi aux(26, INT_MAX);
      F0R(j, 26) {
        F0R(l, 26) {
          aux[l] = min(aux[l], dp[j] + v[j][l] + v[l][j]);
        }
      }
      dp = aux;
    }
  }
  if (k % 2 == 0) {
    vi aux(26, INT_MAX);
    dp = aux;
    F0R(i, 26) {
      dp[i] = min(dp[i], v[i][i]);
    }
    for (int i = 2; i < k; i += 2) {
      vi aux(26, INT_MAX);
      F0R(j, 26) {
        F0R(l, 26) {
          aux[l] = min(aux[l], dp[j] + v[j][l] + v[l][j]);
        }
      }
      dp = aux;
    }
  }

  int nmin = INT_MAX;
  for (auto x : dp) {
    nmin = min(nmin, x);
  }
  if (nmin == INT_MAX) { ccout(-1); }
  else { ccout(nmin); }
}

int32_t main() {
  // readWriteIO();
  fastIO();
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}