\(x \in \left[0, \lfloor N / 3 \rfloor\right]\) に対して、ABC が \(x\) 個以上するように \(S\) を書き換えることができるのでそのコストの最小値を \(f(x)\) とおきます。また定義域の外では便宜上 \(+\infty\) と考えることで、適宜整数全体の集合全体で定義されているとみなします。

このとき関数 \(f\) は次の性質を満たします。

• \(f\) は凸関数: \(f(x) + f(x + 2) \ge f(x + 1) + f(x + 1)\)
• 定義域内で、\(f(x) \in [0, N]\)

従って、ABC のコスト免除額を二分探索する Alien DP で解くことが出来ます。実行時間は \(O(N \log N)\) です。