Let \(P\) be the sum of vectors chosen in the optimal solution. We organize the conditions under which removing or adding one vector from/to \(P\) does not improve the score.

After some computation, we find the following:

• Removing vector \(v\) from \(P\) does not improve the score \(\iff\) Consider the line through \(v\) perpendicular to \(0 \to v\). Now, consider the intersection point \(z\) of this line and the line \(0 \to P\). Then, \(|z| \leq \frac{2}{3+1} |P|\).

• Adding vector \(v\) to \(P\) does not improve the score \(\iff\) Consider the line through \(v\) perpendicular to \(0 \to v\). Now, consider the intersection point \(z\) of this line and the line \(0 \to P\). Then, \(|z| \geq \frac{2}{3-1} |P|\).

We construct the solution using the fact that \(\frac{2}{3+1} |P|\) and \(\frac{2}{3-1} |P|\) are two times apart.

For \(R=1,2,4,8,\cdots,2^{30}\), we perform the following computation.

Consider a circle \(C_R\) centered at the origin with radius \(R\). While scanning the circumference of this circle, we switch the use/non-use of each vector and update the solution.

For each vector \(v\) (\(|v| \leq R\)), consider the line through \(v\) perpendicular to \(0 \to v\). Cut the circumference with this line, and use vector \(v\) on the arc that does not contain the origin.

It can be proved that among the solution candidates tried in this way, the optimal solution is necessarily included.

First, for some \(R\), we have \(\frac{2}{3+1} |P| \leq R \leq \frac{2}{3-1} |P|\). Then, when we reach a point on \(C_R\) in the direction of \(P\), considering which vectors are being used, we find that it is exactly the optimal solution itself.

Now, we just need to implement the above operation directly. The time complexity is \(O(N \log N \log (\sum |A_i|+|B_i|))\).

Sample solution (C++)