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

Вам очень нужно собрать некоторую строку t. Для этого Вы заранее приготовили n некоторых строк s1, s2, ..., sn. Чтобы собрать строку t, Вам разрешатся выполнить ровно |t| (|t| — длина строки t) операций с этими строками. Каждая операция имеет следующий вид:

  1. выбрать любую непустую строку из строк s1, s2, ..., sn;
  2. выбрать произвольный символ выбранной строки и записать его на листок бумаги;
  3. удалить выбранный символ из выбранной строки.

Заметьте, что после применения описанной операции общее количество символов в строках s1, s2, ..., sn уменьшится на 1. Считается, что вы собрали строку t, если символы, записанные на листок бумаги, в порядке применения операций образуют строку t.

Однако есть и другие ограничения. Для каждой строки si Вам известно число ai — максимальное количество символов, которое разрешается удалить из строки si. Также известно, что каждая операция, в результате которой из строки si удаляется символ, имеет цену i рублей. То есть, операция над строкой s1 самая дешевая (она стоит 1 рубль), а операция над строкой sn — самая дорогая (она стоит n рублей).

Вам нужно посчитать, какое наименьшее количество денег (в рублях) потребуется, чтобы собрать строку t по описанным правилам. Считайте, что стоимость сборки строки t — это сумма цен использованных Вами операций.

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

В первой строке входных данных записана строка t — строка, которую Вам нужно собрать.

Во второй строке записано единственное целое число n (1 ≤ n ≤ 100) — количество строк, к которым разрешается применять описанную операцию. В каждой из следующих n строк записаны строка и целое число. В i-ой строке через пробел записаны строка si и целое число ai (0 ≤ ai ≤ 100). Число ai обозначает максимальное количество символов, которое можно удалить из строки si.

Все строки во входных данных состоят только из строчных латинских букв. Все строки непустые. Длины всех строк не превосходят 100 символов.

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

Выведите единственное число — наименьшее количество денег (в рублях), которое потребуется, чтобы собрать строку t. Если решения не существует, выведите -1.

Примеры
Входные данные
bbaze
3
bzb 2
aeb 3
ba 10
Выходные данные
8
Входные данные
abacaba
4
aba 2
bcc 1
caa 2
bbb 5
Выходные данные
18
Входные данные
xyz
4
axx 8
za 1
efg 4
t 1
Выходные данные
-1
Примечание

Пояснения к примерам:

В первом примере из первой строки нужно взять символы «b» и «z» по цене 1 рубль, из второй строки символы «a», «e» и «b» по цене 2 рубля. Стоимость строки t в таком случае 2·1 + 3·2 = 8.

Во втором примере из первой строки нужно взять два символа «a» по цене 1 рубль, из второй строки символ «c» по цене 2 рубля, из третьей строки два символа «a» по цене 3 рубля, из четвертой строки два символа «b» по цене 4 рубля. Стоимость строки t в таком случае 2·1 + 1·2 + 2·3 + 2·4 = 18.

В третьем примере решения не существует, потому что ни из одной строки невозможно получить символ «y».