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