Observations

Let \(c_i\) be the number of tea bags of flavor \(i\) that the dealer chooses in step 2.

In a game of difficulty \(b\), if the dealer wants to win, the dealer has to satisfy the following condition for all \(i=1,\dots,i\):

• \(c_i \leq \min(A_i, b-1)\).
  • There are only \(A_i\) tea bags of flavor \(i\), so the count cannot exceed \(A_i\).
  • If you are given \(b\) or more tea bags of flavor \(i\), you may choose those \(b\) tea bags.

Hence, \(x = c_1 + \dots + c_N \leq \sum_{i=1}^{N} \min(A_i, b-1)\) is necessary. (Here, \(\sum_{i=1}^{N} \min(A_i, b-1)\) denotes the sum of \(\min(A_i, b-1)\) over \(i=1,\dots,N\).)

Therefore, if \(x > \sum_{i=1}^{N} \min(A_i, b-1)\), then you can win.

Conversely, if \(x = \sum_{i=1}^{N} \min(A_i, b-1)\), then the dealer can choose the tea bags to satisfy \(c_i = \min(A_i, b-1)\), so you will lose. For \(x < \sum_{i=1}^{N} \min(A_i, b-1)\), the dealer can choose any subset of that, and you will lose.

Thus, the minimum value \(x\) for your victory is \(1 + \sum_{i=1}^{N} \min(A_i, b-1)\). If this value is greater than \(\sum_{i=1}^{N} A_i\), you cannot declare such \(x\), so your victory is impossible.

Implementation

If you naively evaluate \(1 + \sum_{i=1}^{N} \min(A_i, b-1)\) for each query, the overall time complexity becomes \(\Theta(NQ)\), which does not fit in the execution time limit. But in fact, we can interpret this expression as the sum of the following two values, plus one:

• the sum of \(A_i\) over all \(i\) with \(A_i \leq b-1\).
• \((b-1)\) times the number of indices \(i\) with \(A_i > b\).

Now consider precalculating the following values for \(0 \leq y \leq \max A_i\):

• \(sum[y]\): the sum of \(A_i\) over all \(i\) with \(A_i \leq y\).
• \(cnt[y]\): the number of indices \(i\) with \(cnt[y]\).

Then the sought value is equal to \(1 + sum[b-1] + (N - cnt[y])(b-1)\).

To find \(cnt[y]\) and \(sum[y]\), execute the following procedure. (This technique is called cumulative sums.)

1. Initialize all \(cnt[y]\) and \(sum[y]\) with \(0\).
2. For \(i=1,\dots,N\), add \(1\) to \(cnt[A_i]\) and \(A_i\) to \(sum[A_i]\).
3. For \(y = 1, \dots, (\max A_i)\) in ascending order, set \(cnt[y]\) to \(cnt[y-1] + cnt[y]\), and \(sum[y]\) to \(sum[y-1]+sum[y]\).

By this algorithm, the computational complexity is \(O(N + \max A_i)\) time for the precalculation and \(O(1)\) time per query, for a total of \(O(N + \max A_i + Q)\) time; this fits in the execution time limit.

Sample code (C++)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <set>
#include <map>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;
using std::set;
using std::map;

typedef long long int ll;

ll n, q;
vector<ll> a;


const ll maxv = 1'000'009;

ll accum_sum[maxv + 1];
ll accum_cnt[maxv + 1];

void solve () {
	for (ll i = 0; i < n; i++) {
		accum_sum[a[i]] += a[i];
		accum_cnt[a[i]] += 1;
	}
	for (ll i = 1; i <= maxv; i++) {
		accum_sum[i] += accum_sum[i-1];
		accum_cnt[i] += accum_cnt[i-1];
	}
	// accum_sum[i] := a[0] + ... + a[i]
	// accum_cnt[i] := number of x s.t. a[x] <= i 

	for (ll qi = 0; qi < q; qi++) {
		ll b;
		cin >> b;

		ll ans = 1 + accum_sum[b-1] + (n - accum_cnt[b-1]) * (b-1);
		if (accum_cnt[b-1] == n) {
			cout << "-1" << "\n";
		} else {
			cout << ans << "\n";
		}
	}
	
	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}

	solve();

	return 0;
}