最適解で選んだベクトルの総和を \(P\) とおきます． \(P\) からベクトルを \(1\) 個引く，あるいは \(1\) 個足す，でスコアが改善しない条件を整理します．

計算すると，以下のようになっていることがわかります．

• ベクトル \(v\) を \(P\) から引いて改善しない \(\iff\) \(v\) を通り，\(0 \to v\) に垂直な直線を考える．この直線と直線 \(0 \to P\) の交点 \(z\) を考える．このとき，\(|z| \leq \frac{2}{3+1} |P|\) である．

• ベクトル \(v\) を \(P\) に足して改善しない \(\iff\) \(v\) を通り，\(0 \to v\) に垂直な直線を考える．この直線と直線 \(0 \to P\) の交点 \(z\) を考える．このとき，\(|z| \geq \frac{2}{3-1} |P|\) である．

\(\frac{2}{3+1} |P|\) と \(\frac{2}{3-1} |P|\) が \(2\) 倍離れていることを使って解法を組み立てます．

\(R=1,2,4,8,\cdots,2^{30}\) について，以下の計算を行えばよいです．

原点中心，半径 \(R\) の円 \(C_R\) を考えます． この円周上を走査しながら，各ベクトルの使用/不使用を切り替えて解を更新します．

各ベクトル \(v\) (\(|v| \leq R\))について，\(v\) を通り，\(0 \to v\) に垂直な直線を考えます．この直線で円周を切り，原点を含まない側にある孤の上ではベクトル \(v\) を使用することにします．

こうして試した解の候補の中に，かならず最適解が含まれていることが証明できます．

まず，いずれかの \(R\) において，\(\frac{2}{3+1} |P| \leq R \leq \frac{2}{3-1} |P|\) が成立します． そして，\(C_R\) 上で \(P\) の方向にある点に来たとき，どのベクトルを使用しているか考えると，まさに最適解そのものだとわかります．

あとは上記の操作をそのまま実装すればよいです． 計算量は \(O(N \log N \log (\sum |A_i|+|B_i|))\) です．

回答例(C++)