Once a price is fixed, the sell is solely dependent on how many people buys it, so we can rearrange \((B _ i) _ i\). Now, suppose that \(B _ 1\geq B _ 2\geq\cdots\geq B _ N\).

Obviously, it is optimal to gouge so far as the number of people who buys it does not reduce. More precisely, we can assume that the possible prices are one of \(B _ i+C _ j\) (otherwise, we can set to a higher price equal to the minimum \(B _ i+C _ j\) greater than the current price without losing a potential customer.)

Then, when \(i\) people buy the item, the gross sales is \(i(B _ i+C _ j)\). Since the maximum value over \(i=1,2,\ldots,N\) is the answer to \(j\), this problem has been boiled down to evaluating the following function \(f(x)\) at each \(x=C _ j\ (1\leq j\leq M)\): \[f(x)=\max _ {1\leq i\leq N}\left\{i(x+B _ i)\right\}.\] The problem in this form can be interpreted as a maximum value problem of the \(y\) coordinates of the intersections of \(x=C _ j\) and a set of lines \(l _ i\colon y=i(x+B _ i)\) in an \(xy\)-plane.

For a set of line \(l_i:y=a _ ix+b _ i\), the maximum \(y\) coordinate of the intersections with the line \(x=\alpha\) can be found with a method called convex Hull Trick.

The Convex Hull Trick is an algorithm to manage a set of lines by tracking a convex region \(S\coloneqq\{(x,y)\mid {}^\forall i.\ y\geq a _ ix+b _ i\}\) on an \(xy\)-plane.

In this problem, the set of liens is static, and prefetching \(C _ 1,\ldots,C _ M\) is also possible, so using the trick leads to a correct answer (no matter which of the several possible implementation courses you take).

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;
    vector<unsigned long> B(N);
    for (auto &&b : B) cin >> b;
    sort(begin(B), end(B), greater<>{});

    vector<tuple<unsigned long, unsigned long, unsigned long>> B_convex{{0, 1, B[0]}};
    for (unsigned i{1}; i < N; ++i) {
        unsigned long x, a{i + 1}, b{a * B[i]};
        do {
            const auto&[x_prev, a_prev, b_prev]{B_convex.back()};
            x = (b_prev + a - min(b_prev + a, b + a_prev)) / (a - a_prev);
            if (x_prev < x) break;
            B_convex.pop_back();
        } while (!empty(B_convex));
        B_convex.emplace_back(x, a, b);
    }

    for (unsigned i{}, c; i < M; ++i) {
        cin >> c;
        const auto&[_, a, b]{*prev(upper_bound(begin(B_convex), end(B_convex), make_tuple(c + 1, 0UL, 0UL)))};
        cout << a * c + b << " ";
    }
    cout << endl;

    return 0;
}