1478: Збирання рядка

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 18
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Необх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

Коментарі

Ще немає коментарів.