First, we assume that the input is sorted in ascending order of \(B\). Also, assume that the answer when choosing zero elements is \(\mathrm{-inf}\).

In our solution, we apply divide-and-conquer algorithm to solve a subproblem where elements are chosen for a segment \([l, r)\). It is trivial when \(r - l = 1\). Otherwise, let \(\displaystyle m = \lfloor \frac{l + r}{2} \rfloor\), and solve the problem for segments \([l, m)\) and \([m, r)\) recursively.

Consider the case where elements are chosen from both segments \([l, m)\) and \([m, r)\). Note that \(\displaystyle \max_{i \in S} B\) only depends on the elements chosen from \([m, r)\). Then, denoting by \(x_i\) the sum of the \(i\) elements with the largest \(A\) among \([l, m)\), and by \(y_i\) that among \([m, r)\), it suffices to find \(\displaystyle z_i = \max_{j + k = i} (x_j + y_k)\).

Here, by definition \(x\) is concave by definition, which can be convolved fast. See also CodeForces blog by errorgorn for more details. If the sequences have both \(M\) elements, it can be computed in \(O(M \log M)\) using Monotone Minima or Li Chao Tree, or in \(O(M)\) using SMAWK algorithm. (The original blog introduces a solution with Li Chao Tree, but it requires a smartly generalized implementation although works intuitively; it is also effectively slower than Monotone Minima.)

Therefore, the problem has been solved in a total of \(O(N \log^2 N)\) time, including divide-and-conquer part. With a more ingenious sort and SMAWK algorithm, it can even be solved in \(O(N \log N)\) time.

Sample code with Monotone Minima (C++)