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