{"problem":{"name":"C. Regular Bracket Sequence","description":{"content":"You are given a bracket sequence $s$ of length $n$. The string consists of opening brackets '_(_' and closing brackets '_)_' only. In one move,  Your task is to find the minimum number of coins requ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10276C"},"statements":[{"statement_type":"Markdown","content":"You are given a bracket sequence $s$ of length $n$. The string consists of opening brackets '_(_' and closing brackets '_)_' only.\n\nIn one move, \n\nYour task is to find the minimum number of coins required to obtain *regular bracket sequence* from $s$. You can perform any number of moves (including zero).\n\nRecall what the regular bracket sequence is:\n\nFor example, \"_ _\", \"_(())()_\", \"_(())_\" and \"_()_\" are regular bracket sequences, but \"_)(_\", \"_()(_\" and \"_)))_\" are not.\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.\n\nEach query contains two lines. The first line contains three integer $n (1 <= n <= 10^5)$: length of string, $a (1 <= a <= 10^9)$: cost of first operation , $b (1 <= b <= 10^9)$: cost of second operation, all separated by space, and \n\nThe second line contains a string consisting of opening and closing brackets only of length $n$.\n\nIt is guaranteed that the total sum of $n$ is at most $10^5$.\n\nPrint $t$ answers to the test cases. Each answer must be consisting of single integer — the minimum coins required to obtain a regular bracket sequence from $s$.\n\nNote: Cost may be greater than $2^(32) -1$.\n\nIn the first query — Choose $i = 1$, remove $1 s t$ character and insert in end to form \"_()_\".\n\nIn the second query — Choose $i = 1$, remove $1 s t$ character and Choose $i = 2$, remove $2 n d$ character to form \"_ _\".\n\nIn the third query — Choose $i = 1$, remove $1 s t$ character to form \"_()_\".\n\n## Input\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains two lines. The first line contains three integer $n (1 <= n <= 10^5)$: length of string, $a (1 <= a <= 10^9)$: cost of first operation , $b (1 <= b <= 10^9)$: cost of second operation, all separated by space, and The second line contains a string consisting of opening and closing brackets only of length $n$.It is guaranteed that the total sum of $n$ is at most $10^5$.\n\n## Output\n\nPrint $t$ answers to the test cases. Each answer must be consisting of single integer — the minimum coins required to obtain a regular bracket sequence from $s$.Note: Cost may be greater than $2^(32) -1$.\n\n[samples]\n\n## Note\n\nIn the first query — Choose $i = 1$, remove $1 s t$ character and insert in end to form \"_()_\".In the second query — Choose $i = 1$, remove $1 s t$ character and Choose $i = 2$, remove $2 n d$ character to form \"_ _\".In the third query — Choose $i = 1$, remove $1 s t$ character to form \"_()_\".","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ T = \\{(n_k, a_k, b_k, s_k) \\mid k \\in \\{1, \\dots, t\\}\\} $ be the set of test cases, where for each $ k $:  \n- $ n_k \\in \\mathbb{Z} $ is the length of the bracket sequence.  \n- $ a_k, b_k \\in \\mathbb{Z}^+ $ are the costs of two operations.  \n- $ s_k \\in \\{ \\texttt{(}, \\texttt{)} \\}^{n_k} $ is a bracket string.  \n\n**Operations**  \n1. **Operation 1 (cost $ a $)**: Remove any single character and insert it at any position.  \n2. **Operation 2 (cost $ b $)**: Remove any single character (and discard it).  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10^5 $  \n2. $ 1 \\le n_k \\le 10^5 $, $ 1 \\le a_k, b_k \\le 10^9 $  \n3. $ \\sum_{k=1}^t n_k \\le 10^5 $  \n\n**Objective**  \nFor each test case $ k $, find the minimum cost to transform $ s_k $ into a *regular bracket sequence* using any number of Operation 1 and/or Operation 2.  \n\nLet $ \\text{balance} $ be the running sum: +1 for '(', -1 for ')'.  \nLet $ \\text{min\\_balance} $ be the minimum value of balance during traversal.  \nLet $ \\text{total\\_open} $ be the number of '(' in $ s_k $, $ \\text{total\\_close} $ be the number of ')' in $ s_k $.  \n\nDefine:  \n- $ \\text{deficit} = \\max(0, -\\text{min\\_balance}) $ — number of '(' needed to fix prefix imbalance.  \n- $ \\text{excess} = \\text{total\\_close} - \\text{total\\_open} $ — surplus closing brackets.  \n- $ \\text{required\\_open} = \\text{deficit} $  \n- $ \\text{required\\_close} = \\max(0, \\text{total\\_open} - \\text{total\\_close}) $  \n\nA regular sequence requires:  \n- Total open = total close → $ \\text{total\\_open} = \\text{total\\_close} $  \n- Balance never drops below 0  \n\nThus, the number of unmatched closing brackets that must be removed or moved: $ \\max(0, -\\text{min\\_balance}) $  \nThe number of excess brackets to eliminate: $ |\\text{total\\_open} - \\text{total\\_close}| $  \n\nLet $ r = |\\text{total\\_open} - \\text{total\\_close}| $  \nLet $ d = \\max(0, -\\text{min\\_balance}) $  \n\nWe must:  \n- Fix prefix imbalance $ d $: can be done by moving $ d $ closing brackets from front to end (cost $ d \\cdot a $) or removing $ d $ closing brackets (cost $ d \\cdot b $)  \n- Fix length imbalance $ r $: must remove $ r $ excess brackets (cost $ r \\cdot b $)  \n\n**Objective Function**  \n$$\n\\min \\left( d \\cdot a + r \\cdot b, \\, (d + r) \\cdot b \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10276C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}