← 返回题目列表

Codeforces · 796/E

E. 考试作弊

中文机器翻译题面 查看原题

赞恩和赞恩的暗恋对象刚刚决定约会!然而,这个女孩在物理期末考试中遇到了问题,需要你的帮助。

有 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 个问题。