Loyalty

Let

$$T=\sum_{i=1}^{n} a_i.$$

After all purchases, the final loyalty level is

$$\left\lfloor \frac{T}{X}\right\rfloor.$$

Also, since every item has price at most $X$, buying one item can increase the loyalty level by at most one. Therefore the number of purchases that give bonus points is fixed:

$$k=\left\lfloor \frac{T}{X}\right\rfloor.$$

So we are not maximizing how many bonus events happen. That number is already locked in. The store did the math, rude but fair. We only choose which $k$ items become bonus items.

The maximum possible score is clearly the sum of the $k$ largest prices. No order can score more, because only $k$ items score. So if we can build an order where the $k$ largest prices are exactly the trigger purchases, we are done.

Trigger Condition

Suppose the current total spent is $S$, and define

$$r=S\bmod X.$$

Buying an item of price $p$ increases the loyalty level exactly when

$$r+p\ge X.$$

If this happens, we earn $p$ points, and the new remainder is

$$(r+p)\bmod X.$$

So we want to use smaller non-scoring items to build up the remainder, then use a large scoring item to cross the next multiple of $X$.

Construction

Sort the prices increasingly.

Split them into two groups:

• small: the first $n-k$ elements,
• big: the last $k$ elements.

The answer value is

$$\sum_{b\in big} b.$$

Now build the order like this:

1. Maintain rem, the current total modulo $X$.
2. Process big from smallest to largest.
3. For the current big item $b$, while rem + b < X, output the smallest unused item from small and add it to rem.
4. Output $b$.
5. Now $b$ triggers bonus, so set rem = (rem + b) % X.
6. After all big items are used, append the remaining small items.

Why Small Items Do Not Steal Bonus

When we output a small item, we are inside the loop where

$$rem+b<X.$$

Every unused small item $s$ is at most $b$, because all small items are outside the largest $k$ elements, and the big items are processed from smallest to largest. Therefore

$$rem+s\le rem+b<X.$$

So no small item triggers bonus. Nice. The cheap stuff stays padding.

Why Each Big Item Triggers

The loop before $b$ stops only once

$$rem+b\ge X.$$

Then buying $b$ increases the loyalty level, so $b$ earns bonus points.

Why We Cannot Run Out Of Padding

Assume we are about to process some big item $b$, and we have already created some number of crossings. If even after using all remaining small items we still had rem + b < X, then the current item plus all available padding would contribute less than one full block of size $X$.

All future big items are at most $X$ each. If there are $m$ future big items, they can contribute at most $mX$. So the remaining total would be less than

$$X+mX=(m+1)X.$$

But from this point onward, the final total still needs exactly $m+1$ more loyalty increases. That requires at least $(m+1)X$ remaining mass after including the current remainder. Contradiction.

So the greedy always has enough padding to make the current big item trigger.

Optimality

There are exactly $k$ bonus purchases in every possible order. Our construction makes exactly the $k$ largest prices become those bonus purchases. Therefore the score is the maximum possible.

Complexity

Sorting dominates:

$$O(n\log n)$$

per test case. The construction is linear. Since the total $n$ over all test cases is at most $10^5$, this easily fits.