F. Быстрый набор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа в записной книжке $$$n$$$ телефонов, про каждый он знает сам номер $$$s_i$$$ и $$$m_i$$$ — сколько раз в день он его набирает.

Недавно Поликарп приобрел совершенно новый телефон с инновационной опцией быстрого набора! Более точно, $$$k$$$ его клавишам можно назначить некоторый номер (не обязательно из телефонной книги). Для ввода номера Поликарп может нажать одну из этих $$$k$$$ клавиш, а потом завершить набор номера нажатиями на обычные цифровые клавиши (ввод номера только цифровыми клавишами также возможен).

Клавиша быстрого набора может быть нажата только когда ни одной цифры еще не набрано. Нельзя переназначать номера на клавиши быстрого набора.

Сколько минимально нажатий цифровых клавиш ему придётся делать в сутки, если он назначит на клавиши быстрого набора номера оптимальным способом?

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

В первой строке записаны два целых числа $$$n$$$ and $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le 10$$$) — количество номеров в телефонной книге Поликарпа и количество клавиш быстрого набора на его новом телефоне.

В $$$i$$$-й из следующих $$$n$$$ строк записана строка $$$s_i$$$ и целое число $$$m_i$$$ $$$(1 \le m_i \le 500)$$$, где $$$s_i$$$ — непустая строка из цифр от $$$0$$$ до $$$9$$$ включительно ($$$i$$$-й номер), а $$$m_i$$$ — и сколько раз в день он будет набран, соответственно.

Гарантируется, что суммарная длина номеров не превысит $$$500$$$.

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

Выведите единственное число — сколько минимально нажатий цифровых клавиш Поликарпу придётся делать в сутки, если он назначит на клавиши быстрого набора номера оптимальным способом.

Примеры
Входные данные
3 1
0001 5
001 4
01 1
Выходные данные
14
Входные данные
3 1
0001 5
001 6
01 1
Выходные данные
18
Примечание

На единственной клавише цифрового набора в первом примере должно быть записано «0001». Тогда суммарное количество нажатий цифровых клавиш будет равно $$$0 \cdot 5$$$ для первого номера + $$$3 \cdot 4$$$ для второго + $$$2 \cdot 1$$$ для третьего. $$$14$$$ в сумме.

На единственной клавише цифрового набора во втором примере должно быть записано «00». Тогда суммарное количество нажатий цифровых клавиш будет равно $$$2 \cdot 5$$$ для первого номера + $$$1 \cdot 6$$$ для второго + $$$2 \cdot 1$$$ для третьего. $$$18$$$ в сумме.