解く問題数を固定してなむか君が \(k\) 問、なぷか君が \(N-k\) 問を解くとしたとき、なむか君は \(A_i-B_i\) が小さい \(k\) 問を、なぷか君は \(A_i-B_i\) が大きい \(N-k\) 問を解くと時間の総和は最小になります。

答えは変わらないので、 \((A_i,B_i)\) を \(A_i-B_i\) で昇順にソートします。

すると \(k\) を固定したときの時間の総和の最小値は \(\sum_{i=1}^{k} A_i+\sum_{i=k+1}^{N} B_i+\sum_{i=0}^{k-1} C_i+\sum_{i=0}^{N-k-1} D_i\) と表せ、これを \(X_k\) とします。

求める答えは \(\min(X_0,X_1,\dots,X_{N-1},X_N)\) です。

前計算で \(A,B,C,D\) それぞれの累積和をとると各 \(k\) について \(X_k\) を \(\Theta(1)\) 時間で求めることができます。前計算にかかる時間は、ソートが \(\Theta(N \log N)\) 、累積和をとるのが \(\Theta(N)\) なので全体で\(\Theta(N\log N)\) 時間で求められます。