Build a directed graph with an edge $x_j\to y_j$ for every command. Only the presence of a symbol matters, not its number of occurrences.

Call an absent symbol a hole. Initially there are no holes. Executing $x\to y$ has three possible effects:

• If $x$ is absent, nothing changes.
• If $x$ and $y$ are present, a new hole appears at $x$.
• If $x$ is present and $y$ is absent, the hole moves from $y$ to $x$.

Thus holes are created but never destroyed, and they move against the edges. If the final holes form a set $H$, our loss is $\sum_{v\in H}a_v$.

Every vertex with an outgoing edge must be a hole at some moment: immediately after executing that edge, its source is absent. Conversely, whenever a vertex is a hole, we can execute all of its outgoing commands without changing anything.

So our task is to visit every vertex with outgoing edges using holes, while minimizing the total value of their final positions.