#!python3
import math

def main():
    n, k = map(int, input().split())
    SIGMA = 26
    costs = [[math.inf for _ in range(SIGMA)] for _ in range(SIGMA)]
    for _ in range(n):
        rune, cost = input().split()
        costs[ord(rune[0]) - ord('a')][ord(rune[1]) - ord('a')] = int(cost)

    # build the palindrome from the inside out.
    # Say the current ends of the palindrome are X.
    # Then we can make a new palindrome of length + 2 by using runes YX and XY.
    if k % 2 == 1:
        dp = [0 for _ in range(SIGMA)]
    else:
        dp = [costs[i][i] for i in range(SIGMA)]

    steps = (k - 1) // 2
    for _ in range(steps):
        ndp = [math.inf for _ in range(SIGMA)]
        for x in range(SIGMA):
            for y in range(SIGMA):
                w = costs[x][y] + costs[y][x]
                ndp[y] = min(ndp[y], dp[x] + w)

        dp = ndp

    answer = min(dp)
    print(-1 if math.isinf(answer) else answer)

if __name__ == "__main__":
    main()