Паладин, воин, искусный в священной магии, нуждается в вашей помощи при создании заклинаний. Поскольку он Паладин, каждое заклинание должно быть палиндромом, то есть читаться одинаково как слева направо, так и справа налево. Стоимость создания нового заклинания основана на стоимости пар рун (стоимости соседних букв), которые встречаются в итоговом заклинании. Пары рун, не представленные во входных данных, использовать в итоговом заклинании нельзя.

Общая стоимость заклинания — это сумма стоимостей всех пар рун в заклинании с учетом количества вхождений каждой пары. Например, если заклинание — abacaba, то стоимость равна сумме стоимостей ab + ba + ac + ca + ab + ba.

Определите наименьшую стоимость создания нового заклинания Паладина ровно заданной длины.

Входные данные

Первая строка входных данных содержит два целых числа $n$ ($1 \le n \le 676$) и $k$ ($2 \le k \le 100$), где $n$ — количество пар рун, а $k$ — желаемая длина заклинания в рунах (то есть буквах).

Каждая из следующих $n$ строк содержит строку $s$ ($s$ состоит ровно из двух строчных латинских букв, которые могут быть одинаковыми или разными) и целое число $c$ ($1 \le c \le 100$), где $s$ — пара рун, а $c$ — стоимость этой пары. Все пары рун различны.

Выходные данные

Выведите единственное целое число — наименьшую возможную стоимость создания заклинания длины $k$ из данных рун, или $-1$, если это невозможно.

Примеры

Входные данные 1

5 9
ab 4
ba 1
bd 3
db 100
bc 4

Выходные данные 1

20