P10115 [LMXOI Round 1] Placer

LMX has recently become obsessed with bracket sequences, and she especially likes valid bracket sequences. To test HQZ’s sincerity, LMX made a problem to challenge HQZ.

LMX gives a bracket sequence $S$ of length $n$, and a sequence $a_i$ of length $n$. Define $w(l,r)= \begin{cases} a_r-a_l, & S_{l..r} \text{ is a valid bracket sequence}\\ \ 0 & \text{otherwise} \end{cases}$ You can split the sequence into several non-empty subsegments. Define the beauty of the whole sequence as the sum of $w(l, r)$ over all segments. Find the maximum possible beauty.

The first line contains an integer $n$. The second line contains a string representing the bracket sequence. The third line contains the sequence $a$.

The first line contains an integer, representing the maximum beauty.

**Sample Explanation #1** The original string can be divided into three intervals: $[1,2],[3,3],[4,5]$. The contribution is $(a_2-a_1)+0+(a_5-a_4)=(3-1)+0+(5-3)=4$. | Subtask ID | $n$ | Special Property | Score | | :--------: | :--------: | :-------------: | :--: | | Subtask #1 | $\le 5000$ | None | $30$ | | Subtask #2 | $\le 10 ^ 5$ | None | $20$ | | Subtask #3 | $\le 3 \times 10 ^ 6$ | The bracket sequence is $()()\dots()$ | $15$ | | Subtask #4 | $\le 3 \times 10 ^ 6$ | None | $35$ | For $100\%$ of the testdata, $1 \le a_i \le 10^9$. Translated by ChatGPT 5