사탕 체인

사탕 체인은 사탕을 한 줄로 이어 붙인 것이다. 사탕의 맛은 26가지이고, 각 맛은 알파벳 소문자 a부터 z까지로 나타낸다. 마고는 아주 화려한 사탕 체인을 가게에 진열해 두었다.

수업이 끝나면 아이들이 가게에 와서 사탕 체인의 일부를 산다. 아이마다 원하는 맛이 다르다. 예를 들어 어떤 아이는 맛이 ababi인 조각을 좋아하고 그 조각에 3유로를 낸다. 다른 아이는 맛이 axsa인 조각을 좋아하고 5유로를 낸다.

마고는 사탕 체인에서 조각 하나를 떼어내 아이에게 판다. 조각을 떼어내면 남은 왼쪽 부분과 오른쪽 부분을 다시 이어 붙이고, 이어서 다른 조각을 팔거나 그만둔다.

사탕 체인에서 같은 조각을 여러 번 떼어낼 수 있다면, 그 조각을 한 아이에게 여러 번 팔 수 있다. 마고는 팔지 못하는 사탕을 버리지 않으므로, 떼어낸 조각은 반드시 어느 아이에게든 팔아야 한다. 조각은 뒤집어서 팔 수 있다. 예를 들어 axsa와 asxa는 같은 조각이다. 모든 아이에게 팔 필요는 없고, 파는 순서도 정해져 있지 않다.

마고가 사탕 체인으로 벌 수 있는 최대 금액을 구하라.

• 첫째 줄에 마고의 사탕 체인이 비어 있지 않은 문자열로 주어진다.
• 둘째 줄에 아이의 수 $C$가 주어진다.
• 다음 $C$개 줄에는 아이가 원하는 조각과 그 아이가 낼 금액이 공백 하나로 구분되어 주어진다. 원하는 조각은 비어 있지 않은 문자열이고, 금액은 정수 $P_i$이다.

제한

• 사탕 체인과 각 아이가 원하는 조각은 모두 사탕 50개 이하로 이루어진다.
• $1 \le C \le 200$
• $1 \le i \le C$인 모든 $i$에 대해 $0 \le P_i \le 1000000$
• 모든 문자열은 알파벳 소문자 a부터 z까지로만 이루어진다.

마고가 벌 수 있는 최대 금액을 정수 하나로 출력한다.