Wishing Cards

We need choose integers $b_i$ with

$0\le b_i\le a_i,\qquad \sum b_i\le k$

and maximize

$\sum_{j=1}^n \max(b_1,b_2,\ldots,b_j).$

The trap is thinking every friend matters individually. They do not. Little A only remembers the current biggest pile of cards, so most chosen values are useless noise.

First cleanup

Suppose before friend $i$ the current maximum is $m$. If we choose some $b_i\le m$, the prefix maximum does not change. It adds no future benefit either. Since we are not required to spend exactly $k$ cards, spending those cards is just burning budget for vibes. Bad vibes. Set it to $0$ instead.

So in an optimal solution, every positive nonzero choice is a new record:

$b_i > \max(b_1,\ldots,b_{i-1}).$

That turns the problem into choosing a few record-breaking friends and their record values.

DP state

Process friends left to right. Since $k\le 360$, we can afford states involving card budget and current maximum.

Let

$dp[c][m]$

be the maximum happiness after processing some prefix of friends, having spent exactly $c$ cards, with current prefix maximum equal to $m$.

Impossible states are $-\infty$.

Initially:

$dp[0][0]=0.$

For each friend with capacity $a_i$, we do two conceptual steps.

Step 1: collect happiness for this visit

If the current maximum is $m$, then after this friend's visit Little A gains $m$, unless this friend sets a new record. It is easier to handle this by defining transitions directly for the chosen value at this friend.

For friend $i$, from old state $(c,m)$:

1. Give $0$ cards or anything not exceeding $m$: current maximum stays $m$, cost does not need to increase, gain is $m$.
2. Choose a new record $v$ with $m<v\le a_i$: spend $v$ cards, current maximum becomes $v$, gain is $v$.

So the raw transitions are:

$ndp[c][m] = \max(ndp[c][m], dp[c][m]+m)$

and

$ndp[c+v][v] = \max(ndp[c+v][v], dp[c][m]+v)$

for every $v>m$ and $v\le a_i$.

This is correct, but doing all triples $(c,m,v)$ per friend would be too chunky: about $O(nk^3)$.

Speeding up the record transition

For a fixed new record $v$ and final spent amount $nc$, the previous cost must be

$c = nc-v.$

The previous record $m$ can be anything smaller than $v$:

$m < v.$

Thus we need:

$\max_{m<v} dp[nc-v][m].$

That is just a prefix maximum over $m$ for each budget.

Before processing a friend, build:

$pref[c][v] = \max_{0\le m\le v} dp[c][m].$

Then the best transition that creates record $v$ is:

$pref[nc-v][v-1] + v.$

We only allow it when $v\le a_i$.

Per friend transitions

For each friend:

1. Start $ndp$ as impossible.
2. Keep the old record:

$ndp[c][m] = dp[c][m]+m.$

3. Build prefix maxima of $dp$ over $m$.
4. For every possible new record $v$ from $1$ to $a_i$, and every final cost $nc\ge v$:

$ndp[nc][v] = \max(ndp[nc][v], pref[nc-v][v-1]+v).$

Then replace $dp$ with $ndp$.

The answer is:

$\max_{0\le c\le k}\max_{0\le m\le k} dp[c][m].$

because the total number of cards may be at most $k$, not exactly $k$.

Why this works

The DP considers every relevant optimal action:

• If friend $i$ does not improve the maximum, we can treat them as giving $0$ cards, and the state only gains the old maximum.
• If friend $i$ improves the maximum to $v$, the exact old maximum only matters by being less than $v$, so prefix maxima preserve the best possible previous happiness.
• The cost of setting a new record to $v$ is $v$, not $v-m$. This is the detail that will absolutely murder the solution if ignored.

Since every optimal solution can be viewed as a sequence of record-setting moves plus zeroes, and every such move is represented by the DP, the result is optimal.

Complexity

There are $O(k^2)$ states. For each friend, keeping states costs $O(k^2)$, building prefix maxima costs $O(k^2)$, and trying all new records and budgets costs $O(k^2)$.

So each test case runs in

$O(nk^2)$

with memory

$O(k^2).$

With $k\le 360$ and the given sum constraints, this fits comfortably in C++.