Необхiдно зiбрати деякий рядок ~s~. Для цього у вас є ~n~ рядкiв ~f_1 ,f_2 , . . . f_n ~. Вам можна виконати ~|s|~ операцiй (~|s|~ - довжина рядка ~s~) iз цими рядками. Кожна операцiя може бути однiєю з наступних:

1. Вибрати деякий нерожнiй рядок iз доступних

2. Вибрати довiльний символ iз вибраного рядка i записати його на аркуш паперу

3. Видалити вибраний символ iз вибраного рядка

Є певнi обмеження. Для кожного рядка ~f_i~ вiдоме число ~a_i~ – максимальна кiлькiсть символiв, яку дозволяється видалити iз цього рядка. Також вiдомо, що видалення символа iз рядка ~f_i~ коштує i у.о (операцiя над ~n~-им рядком найдорожча i коштує ~n~ у.о.). Треба визначити, яку найменшу кiлькiсть у.о. треба, щоб зiбрати на паперi рядок ~s~.

Формат вхідних даних

В першому рядку задається ~s~.

В другому рядку мiститься цiле число ~n~.

Наступнi ~n~ рядкiв мiстять ~f_i~ та ~a_i~ . Всi рядки складаються iз маленьких латинських лiтер та не перевищують 100 символiв по довжинi.

Обмеження:

~0 \le a_i \le 100~

~1 \le n \le 100~

~length(f_i) \le 100~

Формат вихідних даних

Вивести найменшу кiлькiсть у.о., необхiдної для збiрки рядка ~s~ або -1, якщо неможливо його зiбрати.

Приклад вхідних даних

abzbe
3
zbb 2
eba 3
ab 10

Приклад вихідних даних

8

Приклад вхідних даних

fzx
4
aew 8
zs 0
efg 5
t 1

Приклад вихідних даних

-1