2855 「CEOI2012」废物回收

译自 CEOI 2012 Day2 T2「Waste Recycling」

回收公司即将处理来自铁路货车的废物。有 $N$ 辆货车在进站的铁轨上等待，而每辆货车只包含一种垃圾。废物处理是根据一个固定的数量设置之一。对于每个设置，我们都给出了一组可用该设置处理的废物类型。遗憾的是，改变设置是一个非常耗时的操作，因此该公司每天使用一个设置。这些货车将按照它们在进入的铁轨上到达的顺序进行处理。为了加快回收速度，公司修建了一条辅助轨道，如下图所示：

这样，如果下一辆货车含有当前设置不能处理的废物，那么它可以被转移到辅助轨道，停放在已经在那里的货车之前。下一辆要加工的货车是进料轨道或辅助轨道的第一排。请注意，任何货车都不能从辅助车道返回进入轨道。该公司希望在未来三天内回收尽可能多的货车的垃圾。在第三天结束时，辅助轨道必须是空的。

你需要写一个程序来计算这三天的设置，这个程序允许处理最多数量的货车，同时保证结束时辅助轨道是空的。如果所有的货车都能在三天内处理完毕，那么您的程序必须给出一个天数最短的解决方案。

注： - 如果当前货车中的废物不能被当前设置处理，则它不能被丢弃。若当前货车在原轨道，则要么停在原处，要么进入辅助轨道；若当前货车在辅助轨道，则它只能停在原处。 - 辅助轨道必须为空，但是原轨道可以不空。

输入的第一行包含三个整数，$N$ 表示货车数量，$K$ 表示废弃物种类的个数，$S$ 表示设置的个数。货车从 $1$ 到 $N$ 编号，废物类型从 $1$ 到 $K$ 编号，设置从 $1$ 到 $S$ 编号。

接下来的 $S$ 行包含设置的描述。输入的第 $(i + 1)$ 行包含一个由空格分隔的整数列表，以 $0$ 结尾，表示一组可以通过设置 $i$ 来处理的废物类型。

最后一行是描述货车的 $N$ 个整数列表：第 $i$ 个数字是货车 $i$ 中包含的废物类型的标识符。对于每种类型 $x$，至少有一个且最多有 $10$ 个设置包含该类型的废物。

输出的第一行包含一个整数，即可以处理的最大货车数。

输出的第二行包含三个以空格分隔的整数，分别是第一天、第二天和第三天的设置。如果两天足够处理所有的货车，那么第三个数字必须是 $0$。同样，如果一天足够，那么第二个数字也必须是 $0$。

如果有多个解决方案，输出任意一个即可。

对于 $50\%$ 的数据，$1 \leq N \leq 10000$，$1 \leq S \leq 300$；
对于 $100\%$ 的数据，$1 \leq N \leq 20000$，$1 \leq K \leq 1000$，$1 \leq S \leq 1000$。

如果只有第一行正确，你将获得该测试点 $40\%$ 的分数。