{"problem":{"name":"A Independent Set","description":{"content":"You are given a string $S$ of length $N$ consisting of `A` and `B`. It is guaranteed that the number of `A`s in $S$ is at most $\\frac{N+1}{2}$. Additionally, you are given a sequence of positive integ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc066_d"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$ of length $N$ consisting of `A` and `B`. It is guaranteed that the number of `A`s in $S$ is at most $\\frac{N+1}{2}$. Additionally, you are given a sequence of positive integers $(x_1, \\ldots, x_{N-1})$.\nOn this string, you can repeatedly perform the following operation:\n\n*   Choose an integer $i$ such that $1\\leq i\\leq N-1$, and swap the $i$\\-th and $(i+1)$\\-th characters of $S$. The cost of this operation is $x_i$.\n\nYour goal is to rearrange $S$ so that no two `A`s are adjacent. Find the minimum total cost required to achieve this goal.\n$T$ test cases are given; solve each of them.\n\n## Constraints\n\n*   $1\\leq T\\leq 10^5$\n*   $2\\leq N\\leq 10^6$\n*   $S$ is a string of length $N$ consisting of `A` and `B`.\n*   The number of `A`s in $S$ is at most $\\frac{N+1}{2}$.\n*   $1\\leq x_i \\leq 10^6$\n*   The sum of $N$ over all test cases in a single input is at most $10^6$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$S$\n$x_1$ $\\ldots$ $x_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc066_d","tags":[],"sample_group":[["5\n4\nBAAB\n3 4 5\n5\nBBBBB\n1 2 3 4\n7\nBAAABBB\n8 7 6 5 4 3\n7\nBAAABBB\n100 7 6 5 4 3\n20\nBAABAABBBABAAABBBABB\n12 85 37 44 25 14 36 29 71 53 15 47 13 80 14 74 53 76 19","3\n0\n13\n15\n133\n\n*   For the first test case, performing the operation with $i=1$ changes $S$ as `BAAB` → `ABAB`, achieving the goal. The total cost in this case is $x_1=3$.\n*   For the second test case, performing nothing achieves the goal. The total cost in this case is $0$.\n*   For the third test case, performing the operation with $i=1$ and $i=4$ changes $S$ as `BAAABBB` → `ABAABBB` → `ABABABB`, achieving the goal. The total cost in this case is $x_1+x_4=13$.\n*   For the fourth test case, performing the operation with $i=4$, $i=3$, and $i=5$ changes $S$ as `BAAABBB` → `BAABABB` → `BABAABB` → `BABABAB`, achieving the goal. The total cost in this case is $x_4+x_3+x_5=15$."]],"created_at":"2026-03-03 11:01:14"}}