[Ceoi2012]wagons

时间限制:1s      空间限制:128MB

题目描述

现在有n个马车在铁路口等着,每个马车上有一种垃圾。我们有一些垃圾处理器,每种垃圾处理器能处理一些特定的垃圾。每天只能用一个垃圾处理器
铁路旁边还有一个栈
n个马车按顺序过去,如果当前的垃圾处理器能处理他,就处理了;否则要么过一天换一个垃圾处理器,要么你可以把它放入栈中
你每次既能处理铁路上的垃圾,也能处理栈中的垃圾……处理有顺序要求,铁路上的垃圾得按顺序处理,栈中的垃圾得按入栈顺序的逆序处理(所以才叫栈)。
每天一个垃圾处理器能处理无限垃圾
你要处理三天垃圾,你需要通过调整三天里分别用哪种垃圾处理器,从而处理最多数目的垃圾,同时还要求三天后栈是空的


输入格式

第一行N,K,S,表示n个马车,有K种垃圾,有S种垃圾处理器,n<=20000,K,S<=1000
接下来S行,每行若干个数,表示垃圾处理器能处理的垃圾集合。每行以0结尾
最后一行N个数表示每辆马车上面的垃圾种类
保证每种垃圾至少一种最多十种垃圾处理器能处理


输出格式

第一行输出最多能处理多少垃圾
第二行输出三个数,分别表示三天的的垃圾处理器
如果第一问答案是n,存在两天的方案,那么要求输出两天的;如果第一问答案是n,存在一天的方案,要求输出一天的
如果存在两天的方案,第三个数字应该是0;如果存在一天的方案,第二、三个数字应该是0


样例输入

13 5 4
1 0
4 5 0
5 3 0
2 5 0
4 5 2 5 5 4 1 1 5 4 5 3 3

样例输出

11
2 1 4

提示

没有写明提示


题目来源

鸣谢Ydc提供SPJ