Emacs++

In 2016's Distributed Code Jam, we introduced the Lisp++ language for Lisp fans who prefer a higher density of parentheses. Here is a reminder of how the syntax works.

A Lisp++ program is a string of balanced parentheses. More formally, a Lisp++ program is one of the following. In this specification, $C$ stands for some program code, which does not have to be the same code each time.

• () A single opening parenthesis followed by a closing parenthesis. This ( matches this ), and vice versa.
• ($C$) A program enclosed in a pair of parentheses. This ( matches this ), and vice versa.
• $CC$ Two programs, not necessarily the same, placed back to back.

This year we announce Emacs++, a text viewer for Lisp++. Emacs++ shows a Lisp++ program of length $K$ as a single long line with a cursor you can move. The cursor is a block cursor that always sits on one of the $K$ characters, never between two characters.

At any point, you can perform one of the following three actions to move the cursor. Let $i$ be the current cursor position, counting from 1 at the leftmost character.

• Move the cursor one character left. If the cursor is already on the leftmost character, nothing happens. This takes $L_i$ seconds.
• Move the cursor one character right. If the cursor is already on the rightmost character, nothing happens. This takes $R_i$ seconds.
• Teleport the cursor to the parenthesis that matches the $i$-th character. This takes $P_i$ seconds.

We want to know how efficient Emacs++ is. There is one Lisp++ program and a list of $Q$ queries about it. Each query has a start position $S_j$ and an end position $E_j$. For the $j$-th query, find the smallest time $N_j$ (in seconds) needed to move the cursor from $S_j$ to $E_j$ when you make optimal decisions.

Output the sum of all $N_j$ values.

The first line contains the number of test cases $T$. Each test case follows.

The first line of a test case contains two integers $K$, the length of the Lisp++ program, and $Q$, the number of queries.

The second line contains a string $P$ of $K$ characters, each ( or ), representing a balanced Lisp++ program.

The third, fourth, and fifth lines each contain $K$ integers. The $i$-th integers on these lines are $L_i$, $R_i$, and $P_i$, respectively.

The sixth and seventh lines each contain $Q$ integers. The $j$-th integers on these lines are $S_j$ and $E_j$, respectively.

For each test case, output one line in the format Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the sum of all $N_j$ values.

• $1 \le T \le 100$.
• $K = 10^5$ and $Q = 10^5$ for at most 9 test cases.
• $2 \le K \le 1000$ and $1 \le Q \le 1000$ in all other cases.
• The length of $P$ is $K$, and $P$ is a string of balanced parentheses as described above.
• $1 \le S_j \le K$ for all $j$.
• $1 \le E_j \le K$ for all $j$.

In the sample case, which obeys the limits for Test Set 1, every move costs 1 second. The shortest times for the queries are as follows.

1. Move right from 7 five times to 12, taking 5 seconds.
2. Teleport from 4 to 11, taking 1 second.
3. Teleport from 4 to 11, then move left to 10, taking 2 seconds.
4. Teleport from 12 to 1, taking 1 second.
5. Move right from 5 to 6, taking 1 second.

The sum of the query times is 5 + 1 + 2 + 1 + 1 = 10 seconds.