Choosing Column Prefixes

Increasing $P_j$ by one adds $A_{P_j+1}+B_j$. Because $A$ is non-increasing, an optimum never needs to take a lower value in a column without taking every value above it. Hence the answer is the sum of the $K$ largest values among all $N^2$ pair sums $A_i+B_j$.

After sorting $B$, the number of pair sums at least an integer $x$ can be counted in $O(N\log N)$ using binary search for every $A_i$. Find the largest for which this count is at least . Sum every pair strictly greater than , then add for the remaining pairs. The answer may exceed 64-bit range, so a 128-bit integer is required.