Cake Collection

The annoying-looking part is that Maple can revisit ovens, and each oven keeps accumulating cakes between visits. That sounds dynamic. It is not. The trick is to stop caring about every visit and care only about the last visit to each oven.

Suppose oven $i$ is collected at times

$t_1 < t_2 < \dots < t_k.$

The collected amount from this oven is

$a_i t_1 + a_i(t_2-t_1) + \dots + a_i(t_k-t_{k-1}) = a_i t_k.$

Everything telescopes. Earlier visits do not change the total contribution of that oven; they only split the same pile into smaller piles. So oven $i$ contributes exactly

$a_i \cdot \text{(last time oven } i \text{ is collected)}.$

If an oven is never collected, its last collection time is $0$, so it contributes $0$.

Reduced problem

Now we just need to choose last collection times.

There are $m$ seconds, so there are only $m$ collection actions. Therefore at most $m$ ovens can have a positive last collection time. Also, of course, there are only $n$ ovens. So only

$k = \min(n,m)$

ovens matter.

Their last collection times must be distinct seconds from $1$ to $m$. To maximize the answer, we should clearly use the largest possible times:

$m-k+1, m-k+2, \dots, m.$

But which oven gets which time?

Greedy ordering

The largest baking rates should get the latest times.

If $a_x > a_y$, but oven $x$ gets time $p$ and oven $y$ gets later time $q$ where $p < q$, their contribution is

$a_xp + a_yq.$

After swapping:

$a_xq + a_yp.$

The difference is

$(a_xq + a_yp) - (a_xp + a_yq) = (a_x-a_y)(q-p) > 0.$

So the swap improves the answer. Therefore any optimal solution must put bigger $a_i$ on bigger times. Greedy wins; the problem politely steps aside.

Algorithm

1. Sort the oven rates in descending order.
2. Let $k = \min(n,m)$.
3. For the first $k$ rates, assign times $m, m-1, \dots, m-k+1$.
4. Add $a_i \cdot time$ to the answer.

The answer can be large: up to about $10^5 \cdot 10^8 \cdot 10^5$, so use long long.

Complexity

Sorting dominates:

$O(n \log n)$

per test case, with total $n$ bounded by $2 \cdot 10^5$, so this is easily fine.