Note for the first two subtasks, there is only one of each toy.

The first subtask rewarded brute-force or suboptimal solutions.

For the second subtask, we realize that this is a bipartite matching problem. To create the graph, construct an edge between the ~i~-th child and each of the toys on their wishlist.

Remember that in a bipartite matching/max flow problem, a source and sink node must be created. In this case, the source node "connects" to each child and the each toy "connects" to the sink node.

Finally, run a cubic-time or better max flow algorithm (e.g. Edmonds-Karp) to obtain the solution.

For the third subtask, notice that if we give the edge between the ~i~-th toy to the sink a weight equal to the quantity of the ~i~-th toy that that Santa can make (~a_i~), we can run the same algorithm to get our answer. Proof is left as an exercise to the reader.

Time complexity: ~\mathcal{O}(N^3)~