AT_agc066_d [AGC066D] A Independent Set

[problemUrl]: https://atcoder.jp/contests/agc066/tasks/agc066_d `A`, `B` からなる長さ $ N $ の文字列 $ S $ が与えられます．ただし，$ S $ に含まれる `A` の個数は $ \frac{N+1}{2} $ 以下であることが保証されます．さらに，正整数列 $ (x_1,\ \ldots,\ x_{N-1}) $ が与えられます． あなたはこの文字列に対して，次の操作を繰り返し行うことができます： - $ 1\leq\ i\leq\ N-1 $ を満たす整数 $ i $ を選び，$ S $ の $ i $ 文字目と $ (i+1) $ 文字目をスワップする．この操作にはコストが $ x_i $ かかる． あなたの目標は，$ S $ において `A` 同士が隣接しないようにすることです．この目標を達成するために必要なコストの総和としてありうる最小値を求めてください． $ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられます． > $ T $ $ \text{case}_1 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられます． > $ N $ $ S $ $ x_1 $ $ \ldots $ $ x_{N-1} $

$ T $ 行出力してください．$ i $ 行目には $ i $ 番目のテストケースについて，$ S $ において `A` が隣接しないようにするために必要なコストの最小値を出力してください．

### 制約 - $ 1\leq\ T\leq\ 10^5 $ - $ 2\leq\ N\leq\ 10^6 $ - $ S $ は `A`, `B` からなる長さ $ N $ の文字列である． - $ S $ に含まれる `A` の個数は $ \frac{N+1}{2} $ 以下である． - $ 1\leq\ x_i\ \leq\ 10^6 $ - $ 1 $ 個の入力に含まれるテストケースについて，それらの $ N $ の総和は $ 10^6 $ 以下である． ### Sample Explanation 1 \- $ 1 $ 番目のテストケースについて，$ i=1 $ として操作を行うことで $ S $ は `BAAB` → `ABAB` と変化し，目標を達成できます．この場合コストの総和は $ x_1=3 $ です． - $ 2 $ 番目のテストケースについて，操作を行わないことで目標を達成できます．この場合コストの総和は $ 0 $ です． - $ 3 $ 番目のテストケースについて，$ i=1 $, $ i=4 $ として操作を行うことで $ S $ は `BAAABBB` → `ABAABBB` → `ABABABB` と変化し，目標を達成できます．この場合コストの総和は $ x_1+x_4=13 $ です． - $ 4 $ 番目のテストケースについて，$ i=4 $, $ i=3 $, $ i=5 $ として操作を行うことで $ S $ は `BAAABBB` → `BAABABB` → `BABAABB` → `BABABAB` と変化し，目標を達成できます．この場合コストの総和は $ x_4+x_3+x_5=15 $ です．