New Year's Gifts

Let’s separate the unavoidable part from the actual choice.

Every friend must receive a gift worth at least $y_i$, and the statement guarantees

$\sum_i y_i \le k.$

So spend that immediately. Define

$B = k - \sum_i y_i$

as the extra budget, and

$c_i = z_i - y_i$

as the extra cost to make friend $i$ happy by money.

Now friend $i$ can be made happy in exactly one of two useful ways:

• pay $c_i$ extra coins;
• assign them a box with beauty at least $x_i$.

Using both is just lighting money on fire, which is usually a bad Codeforces strategy.

Key Reframe

If we pay $c_i$ for a friend, they are happy no matter what box they get. So for the box-matching part, that friend can be treated as removed.

After choosing some upgraded friends, the remaining friends can only be made happy with boxes. We need to know how many of those remaining friends cannot be boxed.

For any threshold $v$, consider all remaining friends with $x_i \ge v$. They can only use boxes with beauty $a_j \ge v$. Therefore, if

$F_v = \#\{\text{remaining friends with } x_i \ge v\}$

and

$G_v = \#\{\text{boxes with } a_j \ge v\},$

then at least

$F_v - G_v$

of those friends cannot get a valid box.

Taking the worst threshold gives the exact number of remaining friends who must stay unhappy:

$D = \max\left(0, \max_v(F_v - G_v)\right).$

Why exact? Because these constraints are nested suffix constraints. A friend requiring beauty at least $5$ is also counted in every lower threshold like $4,3,2,1$. For this kind of chain, Hall’s condition reduces exactly to checking every suffix. If every suffix has enough boxes after allowing $D$ failures, greedy matching works.

So the final number of happy friends is

$n - D.$

Thus we want to spend at most $B$ upgrade coins to make $D$ as small as possible.

Binary Search on the Number of Unhappy Friends

Suppose we allow at most $d$ friends to be unhappy.

For every threshold $v$, after upgrades we need

$F_v \le G_v + d.$

Let $A_v$ be the original number of friends with $x_i \ge v$. If we upgrade $U_v$ friends among those with $x_i \ge v$, then remaining friends in that suffix equal $A_v - U_v$.

So we need

$A_v - U_v \le G_v + d,$

or

$U_v \ge A_v - G_v - d.$

Define

$R_v = \max(0, A_v - G_v - d).$

For this fixed $d$, our job is:

Choose minimum total upgrade cost such that for every $v$, at least $R_v$ upgraded friends have $x_i \ge v$.

If that minimum cost is at most $B$, then $d$ unhappy friends is feasible.

Feasibility is monotonic: if $d$ works, any larger $d$ also works. So binary search the smallest feasible $d$.

Greedy Check for a Fixed $d$

Scan $v$ from $m$ down to $1$.

Maintain a min-heap of upgrade costs of all friends with $x_i \ge v$ that we have not already upgraded.

Also maintain chosen, the number of upgraded friends selected so far. Since we scan downward, all selected friends always have $x_i \ge v$, so they count for the current suffix.

At threshold $v$, we need at least

$R_v = \max(0, A_v - G_v - d)$

selected friends from this suffix.

If chosen < R_v, we must select more friends. The cheapest valid choice is simply the cheapest available cost in the heap. Pop until chosen == R_v.

This greedy is correct because when processing threshold $v$, only friends with $x_i \ge v$ can help. Future lower thresholds will only add more eligible friends, but they cannot help retroactively with stricter higher thresholds. So whenever we are forced to pick, picking the cheapest currently eligible friend is optimal. No drama, no DP circus.

Complexity

For one check, every friend enters the heap once and can be popped at most once, so it costs

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

Binary search adds a factor of $O(\log n)$.

Across all test cases:

$O\left((\sum n + \sum m)\log n \log n\right),$

which is fine for $2 \cdot 10^5$ total input size.