Create or Duplicate

The tempting first move is to solve each present type separately. For one value $x$, residues form a graph with edges $r\to r+x$ costing $x$ and $r\to 2r$ costing $k$. That part is fine. The problem is combining three such distance arrays: you run straight into min-plus convolution, which is where dreams go to die.

The actual trick is to change the viewpoint.

Zero-Start Trick

Solve this variant first: Santa starts with no presents, and must end with at least one present of each type.

If the minimum cost there is $D$, then the original answer is

$D-(a+b+c).$

In the zero-start version, the first copy of each type costs $a$, $b$, and $c$. In the real problem, those exact first copies already exist for free. Everything else can be identical.

Canonical Duplicate Rounds

Consider any zero-start construction. For a fixed type, suppose it is duplicated $p$ times after its first copy appears. A present created before all $p$ duplications contributes $x\cdot 2^p$ to the final sum. A present created later contributes $x\cdot 2^d$ for some smaller $d$.

Now compare different types. If type $A$ needs more future duplications than type $B$, we can delay the first creation of type $B$ until only its needed number of duplicate rounds remain.

So every optimal construction can be rewritten like this:

1. Create some presents.
2. Duplicate every type that has appeared so far, once each.
3. Create more presents, maybe introducing new types.
4. Duplicate every appeared type again.
5. Repeat.

Once a type appears, it participates in every later duplicate round. That is the key. We no longer need separate residues for $a$, $b$, and $c$.

State Graph

Let $v_0=a$, $v_1=b$, $v_2=c$.

A state is

$(r, mask),$

where $r$ is the current total sum modulo $m$, and mask records which types have appeared at least once.

There are only $8m$ states.

Create type $i$:

$$(r, mask) \to ((r+v_i)\bmod m,\ mask\cup\{i\})$$

with cost $v_i$.

Duplicate one synchronized round:

$$(r, mask) \to (2r\bmod m,\ mask)$$

with cost

$k\cdot \operatorname{popcount}(mask).$

Why does the total double? Because this round duplicates every type that has appeared, so every currently represented present gets copied once. Clean. No three-dimensional state explosion nonsense.

Start at $(0,0)$. We need $(0,7)$: total divisible by $m$, and all three types appeared. Run Dijkstra, then subtract $a+b+c$.

Correctness

Every graph path gives a valid zero-start spell sequence. Create edges are literal create spells. A duplicate edge is implemented by duplicating each appeared type once, costing $k$ for each set bit in mask, and doubling the total sum.

Now take any valid zero-start spell sequence. For every created present, define its level as the number of future duplications of its type. Process levels from large to small: create all presents of the current level, then duplicate all types that still need one of these future duplications. Types with fewer total duplications are introduced later. This preserves every final multiplier, every create cost, and every duplicate cost.

So the shortest path in this graph is exactly the zero-start optimum. Subtracting $a+b+c$ converts it back to the original problem.

Complexity

There are $8m$ states and at most four outgoing edges per state. Dijkstra runs in

$O(m\log m)$

per test case. Since $\sum m\le 5\cdot 10^5$, this fits easily.