Let us do a binary search by considering whether the objective can be achieved no later than Day \(D\).

Consider a bipartite graph with \(N \times K + D \) vertices, \(N \times K\) of them representing the pairs of an employee and a medal, and \(D\) of them representing the days.

Let \(U\) be the set consisting of the \(N \times K\) vertices representing the pairs of an employee and a medal.

We will draw an edge from the vertex representing each day to the vertices corresponding to the employees working on that day. Then, the objective is equivalent to the existence of a matching covering \(U\).

By using Hall’s marriage theorem, we can rephrase this condition as \(|A| \leq |\Gamma(A)|\) for every subset \(A\) of \(U\).

The value \(|\Gamma(A)|\) only depends on the set of employees contained in \(A\). Thus, for the vertices corresponding to a certain employee, we just need to consider two cases: the case \(A\) contains none of those vertices and the case \(A\) contains all those vertices.

Therefore, we can solve the problem if, for every non-empty subset of employees, we can find the number of days when at least one of the employees contained in the subset comes to work. We can compute it by finding the set of employees who come to work on each day and applying the fast zeta transform.

Furthermore, \( |A| \leq NK \leq |\Gamma(A)|\) holds on Day \(2 N K\) and later, so we can see that it takes at most \(2 N K\) days to achieve the objective.

The total time complexity of this solution is \(O((NK + N \cdot 2^N) \log(NK))\).