문자열 제거

지우고 싶은 문자열 $S$와 지울 수 있는 문자열 $A_{1}$, $A_{2}$, ..., $A_{M}$이 주어진다. 문자열 $A_{i}$들은 각자 $X_{i}$라는 점수를 가진다. 이 때, 문자열 $S$를 삭제 연산을 이용하여 모두 제거하려고 한다.

삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다.

1. 문자열 $S$의 부분 문자열 중에 문자열 $A_{i}$ 가 존재한다면 해당하는 부분을 지우고 $X_{i}$ 만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다).
2. 문자열 $S$에서 문자 하나를 지우고 점수를 $1$점을 얻을 수 있다.

예를 들어, 문자열 $S$가 "abcxyzxabc"이 있고 "abc" 문자열을 지울 경우 10점, "xyz" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를 얻을 수 있는 과정은 아래와 같다.

• 문자열 $S$에서 문자열 "xyz" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열 $S$는 "abc___xabc"가 된다. 이때, '_'는 문자가 지워진 자리를 의미한다.
• 문자열 $S$에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 $S$는 "______xabc"가 된다.
• 문자열 $S$에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 $S$는 "______x___"가 된다.
• 남은 문자들을 하나씩 지운다. 현재 총 얻은 점수는 26점이고 문자열 $S$는 빈 문자열이 된다.

문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.

삭제 연산을 이용하여 문자열 $S$을 지울려고 할 때 얻을 수 있는 최대 점수는 몇 점인지 계산하자.

첫번째 줄에는 문자열 $S$이 주어진다.

두번째 줄에는 지울 수 있는 문자열 개수 $M$이 주어진다.

세번째 줄부터 $M + 2$ 줄까지 문자열 $A_{i}$와 점수 $X_{i}$이 공백으로 구분되어 주어진다.

문자열 $S$를 모두 제거하여 얻을 수 있는 점수를 출력하자.

• 입력으로 주어지는 문자열을 모두 알파벳 소문자로 구성되어 있다.
• $1 \le |S| \le 1,000$
• $1 \le M \le 100$
• $1 \le |A_{i}| \le 100$
• $1 \le X_{i} \le 10,000$