P6827 "EZEC-4" Brackets

> Lijing feels like yesterday, but in a blink it has been years.$\newline$ The past is still there, but everything has changed.

You are given a sequence consisting of round brackets and $n$ bracket strings. You need to match subsequences (not necessarily contiguous substrings) within the sequence. Each bracket in the main sequence can be matched at most once. One possible way to match a non-contiguous substring is to match ``` ))(``` inside ```)()(```. Each bracket string has a value $v$, meaning the value gained for each matched bracket of this string. Each bracket string can be matched multiple times. You may stop matching at any time, but you cannot start matching another bracket string before finishing the current one. Note that if you skip some brackets in the main sequence to match later ones, you cannot go back to continue matching earlier positions. Find the maximum total value obtainable.

The first line contains an integer $n$, the number of bracket strings. The second line contains a string $k$, the given main sequence. The next $n$ lines each contain a bracket string $a$ and a number $v$. In these $n$ lines, the $i$-th line gives $a_i, v_i$, representing an existing bracket string and the value obtained for matching one bracket in this bracket string.

Output one number $r$, the maximum value that can be obtained.

[Warm Reminder] **To eliminate wrong solutions, the Constraints have been increased. Please pay attention to the impact of constant factors on your program.** [Constraints] **This problem uses bundled testdata.** For $100\%$ of the testdata, $1 \le n \le 500, 1 \le len(k) \le 10^4, 1 \le len(a) \le 300, 0 \le v \le 10^3$. | Subtask | $ n \le$ | $ len(k) \le$ | $ len(a) \le$ | Time | Score | Special Property | | :----------: | :----------: | :----------: | :----------: |:----------: | :----------: |:----------: | | $1$ | $10$ | $7$ | $7$ | $1\text s$ | $5$ | Guaranteed that in the optimal solution, each $a$ is used at most once. | | $2$ | $10$ | $50$ | $8$ | $1\text s$ | $5$ | Random testdata; if you AC Subtask 3, this subtask is not counted in the total score. | | $3$ | $10$ | $1000$ | $8$ | $1\text s$ | $10$ | Guaranteed that in the optimal solution, each $a$ is used at most once. | | $4$ | $100$ | $10^4$ | $8$ | $1\text s$ | $15$ | None. | | $5$ | $500$ | $10^4$ | $8$ | $1\text s$ | $10$ | None. | | $6$ | $500$ | $10^4$ | $300$ | $2.2\text s$ | $60$ | None. | [Sample $1$ Explanation] The best plan is to first match ```(()``` and then match ```()()()``` (note that you can match at most ```()()```), so the answer is $4 \times 3 + 5 \times 4 = 32$. One feasible matching method is the parts enclosed in square brackets: ```(【(()()】)(【()】```. If you first match ```(()```, then match ```()```, and finally match ```(()```, the value is $4 \times 3 + 2 \times 2 + 4 \times 3 = 28$, which is not optimal. Note that we cannot first match ```(()```, then match one bracket of ```()()()```, and finally match ```(()```, because although we may stop matching at any time, we cannot start matching another string before finishing the current one. [Sample $2$ Explanation] The best plan is to first match ```())```, then match ```()))```, and finally match ```())``` (note that you can match at most ```()```), so the answer is $9 \times 3 + 7 \times 4 + 9 \times 2 = 73$. Translated by ChatGPT 5