Alphabet City

First, delete the mental image of streets and signs. Cute story, but the whole thing is just 26 independent resource constraints. Each capital letter is a resource, and names are just bundles of those resources.

Let $cnt_i[c]$ be the number of times character $c$ appears in street name $s_i$. Let

$$T[c] = \sum_{i=1}^{n} cnt_i[c]$$

be the total count of character $c$ across all street names once.

Now fix which order item was lost: $\ell$.

The plant still delivers $m$ copies of every street name except $s_\ell$. So for a character $c$, the available number of letters is

$$m \cdot (T[c] - cnt_\ell[c]).$$

If Al makes $k$ copies of every non-lost street name and also one copy of the lost street name, then the needed number of this same character is

$$k \cdot (T[c] - cnt_\ell[c]) + cnt_\ell[c].$$

So for every character $c$, we need

$$k \cdot (T[c] - cnt_\ell[c]) + cnt_\ell[c] \le m \cdot (T[c] - cnt_\ell[c]).$$

Define

$$x = T[c] - cnt_\ell[c]$$

as the amount of this letter in all other names, and

$$y = cnt_\ell[c]$$

as the amount required by the lost name.

The condition becomes

$$kx + y \le mx.$$

Rearrange it:

$$y \le (m-k)x.$$

This is the key move. Maximizing $k$ is the same as minimizing

$$t = m-k.$$

Then each character demands

$$tx \ge y.$$

There are two cases.

Case 1: $x = 0$

No other street name contains this letter.

If $y > 0$, then the lost street needs a letter that literally does not exist in the remaining order. Not "hard", not "needs binary search", just impossible. Answer is $-1$.

If $y = 0$, this character does not matter.

Case 2: $x > 0$

We need

$$t \ge \left\lceil \frac{y}{x} \right\rceil.$$

Since all 26 letters must work at the same time, the minimum valid $t$ is

$$t_{min} = \max_c \left\lceil \frac{cnt_\ell[c]}{T[c] - cnt_\ell[c]} \right\rceil$$

over all characters where the denominator is positive.

Then the best possible value is

$$k = m - t_{min}.$$

If $t_{min} > m$, even $k=0$ is impossible, because we cannot make one copy of the lost street from the leftover letters. So the answer is $-1$.

Otherwise the answer is $m - t_{min}$.

Notice that this also handles duplicate names correctly. If the lost street name equals another street name, that other copy still contributes letters through $x$. No special casing, no weird string matching nonsense.

Algorithm

1. Count letters for every string: $cnt_i[26]$.
2. Compute total counts $T[26]$.
3. For each lost index $\ell$:
   • initialize $need = 0$;
   • for each character $c$:
     • $y = cnt_\ell[c]$;
     • $x = T[c] - y$;
     • if $x=0$ and $y>0$, this $\ell$ is impossible;
     • otherwise update $need = \max(need, \lceil y/x \rceil)$ when $x>0$;
   • if impossible or $need > m$, print $-1$;
   • else print $m - need$.

The ceiling division is

$$\left\lceil \frac{y}{x} \right\rceil = \frac{y+x-1}{x}$$

with integer division.

Complexity

Counting all strings costs

$$O\left(\sum |s_i|\right).$$

Then we check 26 letters for each of $n$ streets, so

$$O(26n).$$

The memory usage is $O(26n)$ for the per-string counts. With $n \le 2 \cdot 10^5$, this is completely fine. 1300-rated problem, not a boss fight.