Maximum Value Parenthesis Subsequence Matching

Given a main sequence S consisting solely of parentheses (' and ')' and an integer n representing the number of bracket strings, each of which is also a string of parentheses and has an associated value v, you are to select one or more (possibly repeated) matches from S such that the total obtained value is maximized.

A match is defined as a (not necessarily contiguous) subsequence of S which can be used to match a prefix of one of the given bracket strings. If you match k parentheses from a bracket string with value v, you get a reward of k \times v (i.e. every matched parenthesis contributes a value of \(v\)).

However, there are some restrictions:

• Each character in S can be used at most once overall.
• The matching must proceed from left to right. In other words, if you skip some characters in S to match later characters, you cannot go back and use the skipped characters later.
• You cannot start matching a new bracket string until you have finished (or decided to stop early) the current one. (You can stop matching a bracket string at any moment, i.e. you are allowed to choose a prefix.)

For example, one allowed matching is illustrated as follows:
Given the sequence )()(, one may match the subsequence ))(( (by picking characters in order, although not necessarily consecutive) if it forms a prefix of one of the bracket strings.

Your task is to determine the maximum total value you can achieve by optimally choosing which bracket strings (and how many characters from each) to match from S under the above conditions.

In mathematical terms, if you match k characters from a bracket string with reward \(v\), you earn \(k\times v\). Let S be indexed from 0 to \(L-1\) and denote by dp[i] the maximum score achievable using S[i:]. Then:

[ \mathit{dp}[i] = \max\Big{; dp[i+1], ; \max_{\text{for each bracket string }P} ; \big(, k \times v + dp[index]\big)\Big} ]

where k ranges over the number of characters you can match (in order) from the pattern P starting at position i and index is the next position in S after this matching.

inputFormat

The input is given as follows:

1. The first line contains the main sequence S (a non-empty string consisting only of characters '(' and ')').
2. The second line contains an integer n, the number of bracket strings.
3. Then follow n lines. Each of these lines contains a bracket string (a non-empty string of '(' and ')') and an integer v (the reward value per matched parenthesis) separated by a space.

outputFormat

Output a single integer representing the maximum achievable total value.

sample

()
1
() 5

10