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