Цукерковий рядок
Цукеркова ланцюжок — це послідовність окремих цукерок. Цукерки бувають 26 різних смаків, позначених малими літерами від a до z. У Марго в магазині виставлена незвичайна ланцюжок з цукерок.
Після школи діти приходитимуть до неї, щоб купити шматочки цього ланцюга. У кожної дитини свої вподобання. Наприклад, одна дитина любить порції зі смаком ababi і готова заплатити за це 3 євро. Інша дитина любить порції зі смаком axsa і готова заплатити за це 5 євро.
Марго може витягувати частини цукеркової ланцюжка і продавати їх дітям. Коли вона витягує порцію, вона з'єднує залишені ліву та праву частини ланцюжка, а потім продовжує продавати наступні порції або зупиняється.
Одна й та сама послідовність ароматів може бути продана кілька разів одній і тій самій дитині (за умови, що Марго може витягти кілька екземплярів цього аромату зі своєї ланцюжка). Марго ніколи не викидає цукерки, якщо не може їх продати. Вона може змінювати порядок цукерок у порції при їх продажу (наприклад, axsa і asxa вважаються еквівалентними). Марго не зобов'язана обслуговувати всіх дітей і не зобов'язана обслуговувати їх у певному порядку.
Ваше завдання — допомогти Марго обчислити максимальну суму, яку вона може заробити на своїй ланцюжку цукерок.
Вхідні дані
Перший рядок представляє ланцюжок цукерок Марго у вигляді непорожнього рядка символів. Другий рядок містить кількість дітей c (1 ≤ c ≤ 200). Наступні c рядків представляють вподобання кожної дитини у вигляді двох елементів, розділених пробілом: його або її вподобана порція цукерок представлена непорожнім рядком символів; і те, що він або вона готовий заплатити, представлено цілим числом P[i] (0 ≤ P[i] ≤ 10^6 для всіх 1 ≤ i ≤ c).
Усі рядки складаються тільки з малих літер від a до z. Ланцюжок цукерок Марго, як і порція цукерок кожної дитини, складається не більше ніж з 50 цукерок.
Вихідні дані
Виведіть одне ціле число — максимальну суму, яку може заробити Марго.