Arithmetics Competition

We have two piles of cards, and each query asks:

• choose exactly $z$ cards total,
• use at most $x$ cards from $a$,
• use at most $y$ cards from $b$,
• maximize the sum.

The important thing: the query limits only care about counts, not which exact positions. So if we decide to take $k$ cards from Vadim, obviously we take his best $k$ cards. Taking worse cards while leaving better cards unused would be self-sabotage, and we are not doing that today.

Sort both arrays in decreasing order and build prefix sums:

$$A[k] = \text{sum of the largest } k \text{ values in } a$$ $$B[k] = \text{sum of the largest } k \text{ values in } b$$

with $A[0]=B[0]=0$.

Now each query becomes a one-dimensional optimization.

Valid range for Vadim's count

Suppose Vadim takes $k$ cards. Then Kostya takes $z-k$ cards.

Vadim's limit gives:

$$k \le x$$

Kostya's limit gives:

$$z-k \le y \Rightarrow k \ge z-y$$

Also counts cannot be negative or exceed $z$:

$$0 \le k \le z$$

So the valid interval is:

$$L = \max(0, z-y)$$ $$R = \min(x, z)$$

The statement guarantees $z \le x+y$, so this interval is non-empty.

For a fixed valid $k$, the best sum is:

$$f(k)=A[k]+B[z-k]$$

So we need:

$$\max_{L \le k \le R} f(k)$$

A brute force scan is too slow because the interval can be huge and there are many queries.

Why $f(k)$ has one peak

Look at what happens when we increase $k$ by $1$.

We take one more card from Vadim: the next card is $a_{k+1}$.

We take one fewer card from Kostya: the removed card is $b_{z-k}$, because previously Kostya took $z-k$ cards.

So:

$$f(k+1)-f(k)=a_{k+1}-b_{z-k}$$

Since both arrays are sorted decreasing:

• as $k$ increases, $a_{k+1}$ gets smaller or stays equal,
• as $k$ increases, $z-k$ gets smaller, so $b_{z-k}$ gets larger or stays equal.

Therefore:

$$a_{k+1}-b_{z-k}$$

is non-increasing as $k$ increases.

That means $f(k)$ climbs for a while, then stops, then falls. It is a discrete concave/unimodal function. The max is exactly around the place where the slope changes from positive to non-positive.

Binary search the peak

Inside the valid interval $[L,R]$, we can binary search for the largest $k$ such that moving from $k$ to $k+1$ is still profitable.

Moving right improves the answer when:

$$f(k+1)>f(k)$$

Using the difference formula:

$$a_{k+1} > b_{z-k}$$

This condition is monotonic: once it becomes false, it stays false.

So we binary search on $k$ in $[L, R-1]$:

• if $a_{mid+1} > b_{z-mid}$, the function is still increasing there, so the peak is to the right;
• otherwise, the peak is at $mid$ or to the left.

A clean way:

Start with lo = L, hi = R.

While lo < hi:

• mid = (lo + hi) / 2
• if a[mid + 1] > b[z - mid], set lo = mid + 1
• else set hi = mid

At the end, lo is a maximizing count for Vadim. Then the answer is:

$$A[lo]+B[z-lo]$$

Index details

Use 1-indexed sorted arrays for the cards:

• $a[1]$ is Vadim's largest card,
• $b[1]$ is Kostya's largest card.

Prefix sums are 0-indexed by count:

• $A[0]=0$,
• $A[i]=A[i-1]+a[i]$.

The comparison uses:

$$a[mid+1] > b[z-mid]$$

This is valid because mid < R <= z, so z - mid >= 1. Also mid + 1 <= R <= x <= n, so the a index is valid.

Correctness proof

For any query, if exactly $k$ cards are chosen from Vadim, the best such choice is the top $k$ cards of array $a$, and the best $z-k$ cards from Kostya are the top $z-k$ cards of array $b$. Therefore the best value for this fixed $k$ is $A[k]+B[z-k]$.

The only valid values of $k$ are those satisfying all count constraints, which gives:

$$L=\max(0,z-y), \qquad R=\min(x,z).$$

So the query answer is the maximum of $f(k)=A[k]+B[z-k]$ over $k \in [L,R]$.

Now consider the difference:

$$f(k+1)-f(k)=a_{k+1}-b_{z-k}.$$

Because $a$ is sorted decreasing, $a_{k+1}$ is non-increasing as $k$ grows. Because $b$ is sorted decreasing, $b_{z-k}$ is non-decreasing as $k$ grows. Hence the whole difference is non-increasing.

So $f$ is unimodal: it increases while the difference is positive and does not increase after the difference becomes non-positive. The binary search finds the first valid position where moving right is no longer profitable, or the right endpoint if it stays profitable throughout. That position maximizes $f$ on $[L,R]$.

Therefore the algorithm returns the maximum possible sum for every query.

Complexity

Sorting costs:

$$O(n\log n + m\log m)$$

Each query costs:

$$O(\log z)$$

Memory is:

$$O(n+m)$$

This easily fits the limits. No heroic data structure nonsense needed; just sort, prefix sums, and a binary search that actually knows what it is searching for.