Consider the following decision problem: can we let all the reels display \(D\) by time \(T\)? If it can be solved fast enough, then we can perform a binary search over \(T\) to find the minimum duration required to let all of them display \(D\).

The decision problem can be considered as a matching problem that assigns the time to stop each reel. Consider a bipartite graph, whose parts are the vertices corresponding to the reels and those to the time, with an edge between time \(t\) and reel \(i\) if reel \(i\) displays \(D\) at time \(i\); then, the answer is Yes if there is a matching that uses all the reel vertices.

For example, the graph corresponding to the following input against digit \(1\) is as follows. The vertices with prefix t on the left corresponds to times, and those with r on the right to the reels. (Up to time \(5\))

3 4
1212
1233
3312

What is the upper bound of the time? We can assume that every reel is stopped until it shows the digit \(D\) for the \(N\)-th time …(★); otherwise, if there is a wheel that violates the condition, then at least one of the \(N\) first occurrences of \(D\) in that reel does not coincide with any of the timing to stop the other reels, so we can alter the timing to stop them without worsening the duration. Therefore, if it is possible to let all of them display digit \(D\), then it is achievable by time \(NM\).

Also, by the fact (★), we can assume that the degree of a reel vertex is at most \(N\). Therefore, the graph for the matching problem has only \(O(N^2)\) edges, so the decision problem can be solved in an \(O(N^3)\) time by finding the maximum flow with Dinic’s algorithm (where unnecessary time vertices are removed with coordinate compression).

Hence, the problem has been solved in a total of \(O(NM+N^3 d\log N)\) time.