Ttas, an employee of Dadas Company, wants to create a bracket string of length . Each position must contain either an opening bracket ( or a closing bracket ). At position , Ttas receives coins for writing (, or coins for writing ). His total earnings are the sum over all positions.
A regular bracket string satisfies both of the following conditions.
For example, (), (()), and ()() are regular bracket strings, while )( and (() are not.
The company's president, Dadas, specifies intervals . The substring consisting of positions through , in order, must be a regular bracket string. All interval conditions must hold simultaneously.
Each interval is checked using only the characters inside it; brackets outside the interval cannot be used to match them. Positions outside the specified intervals still receive brackets and contribute to the earnings. The whole string need not be a regular bracket string.
Find the maximum total earnings satisfying every condition.
The first line contains the number of test cases . The overall input format is:
For each test case, print the maximum total earnings satisfying all interval conditions on one line.
In the first test case, Ttas can create (())(. The substrings for and are (()) and (), respectively, so both conditions hold. The earnings at the five positions are , , , , and , totaling .
Each test case has the following format:
The first line contains the string length and the number of conditions . The second and third lines give the earnings for placing an opening or closing bracket at each position, respectively. Each of the next lines gives the endpoints of a required interval. The same interval may appear more than once.
| 2 |
| 11 |
|
| 3 | 16 | and . Every condition applies to the whole string. |
| 4 | 19 |
|
| 5 | 21 | The given intervals are pairwise disjoint. No position belongs to more than one interval. |
| 6 | 26 | No additional constraints. |
The conditions force the first four characters to be (()). Position belongs to no required interval, so Ttas chooses the more profitable opening bracket there. The whole string is not regular, but every specified interval is regular.
In the second test case, the same condition appears twice. Creating (()) earns , while ()() earns . The answer is . Repeating an interval does not cause any earnings to be counted again.
In the first test case, the intervals overlap at . The string satisfying both conditions is ()()(), earning . Independently choosing the more profitable bracket at every position would produce )()()(, which violates the conditions.
In the second test case, the string must be (). Both positions earn , so the answer is .
