[,] になる位置の集合 \(x_1,x_2,\cdots,x_k\) が満たすべき条件を考えます．

これらの index は \(k/2\) 個のペアに分解できる必要があります． 今，\((x_1,x_2),(x_3,x_4),\cdots,(x_{k-1},x_k)\) とペアに分けられたとします． 各ペアについて，一般性を失わず \(x_i<x_{i+1}\) とします． このとき，良い括弧列の \(x_i+1\) 文字目から \(x_{i+1}-1\) 文字目が良い括弧列である→長さ偶数であることから，\(x_i\) と \(x_{i+1}\) の偶奇は異なるとわかります．

以上より， \(x_1,x_2,\cdots,x_k\) 内の奇数と偶数の個数が等しいことは必要条件です．そして，これは十分条件でもあります． これは実際に条件を満たす \(x\) があった場合，次のような手順で良い括弧列を構成できることから従います．

まず，\(x\) の要素を昇順に並べます．そして，\(x\) の隣接する \(2\) 要素であって偶奇の異なる \(x_i,x_{i+1}\) を適当にとります．そして，\(x_i,x_{i+1}\) を [,] でペアにして，その内部を()の繰り返しで埋めます．そして，[()()...()()] の部分を除いて，同様の操作を繰り返します．すると，必ず良い括弧列が構成できます．

よって，\(x\) 内の奇数と偶数の個数が等しいことが必要十分です． あとは，\(i\) の偶奇ごとに，\(B_i-A_i\) をソートし，すべての \(0 \leq c \leq N/2\) について，上位 \(c\) 個を選んだ場合のスコアがどうなるか計算し，その最大を取ればよいです． 計算量は \(O(NlogN)\) になります．