赞恩和赞恩的暗恋对象刚刚决定约会!然而,这个女孩在物理期末考试中遇到了问题,需要你的帮助。
有 n 个问题,编号从 1 到 n。问题 i 出现在问题 i + 1 (1 ≤ i < n) 之前。每个问题都不能猜测,因为错误答案将受到巨额惩罚。女孩幸好坐在两个天才中间,所以她要作弊。
然而,天才也有局限性。他们每个人可能知道也可能不知道某些问题的答案。无论如何,可以肯定地假设他们答卷上的答案是绝对正确的。
为了确保她不会被监考员发现,女孩最多会看p次,每次看的次数不超过两位天才之一答卷上的连续k题。当女孩查看答卷上的某个问题时,如果答卷上有该问题的答案,她就会复制该问题的答案,否则什么也不做。
帮助女孩找到她能答对的最大问题数。
输入
第一行包含三个整数 n、p 和 k (1 ≤ n, p ≤ 1, 000, 1 ≤ k ≤ min(n, 50))——分别是问题数、女孩可以浏览的最大次数以及一次可以浏览的最大连续问题数。
第二行以一个整数r(0≤r≤n)开始,表示第一个天才在答卷上回答的问题数。然后跟随 r 个整数 a1, a2, ..., ar (1 ≤ ai ≤ n) - 已回答的问题,以严格递增的顺序给出(即 ai < ai + 1)。
第三行以一个整数s(0≤s≤n)开始,表示第二天才在答卷上回答的问题数。然后跟随 s 个整数 b1, b2, ..., bs (1 ≤ bi ≤ n) - 已回答的问题,以严格递增的顺序给出(即 bi < bi + 1)。
输出
打印一个整数——女孩可以正确回答的最大问题数。
示例
输入 #1
6 2 3 3 1 3 6 4 1 2 5 6
输出 #1
4
输入 #2
8 3 3 4 1 3 5 6 5 2 4 6 7 8
输出 #2
7
注意
令 (x, l, r) 表示查看第 x 个天才答题纸上所有问题 i 的动作,使得 l ≤ i ≤ r。
在第一个样本中,女孩通过执行一系列动作 (1, 1, 3) 和 (2, 5, 6) 可以答对 4 个问题。
在第二个样本中,女孩可以执行一系列操作 (1, 3, 5)、(2, 2, 4) 和 (2, 6, 8) 来答对 7 个问题。