CF796E.Exam Cheating

Zane and Zane's crush have just decided to date! However, the girl is having a problem with her Physics final exam, and needs your help.

There are n questions, numbered from 1 to n. Question i comes before question i + 1 (1 ≤ i < n). Each of the questions cannot be guessed on, due to the huge penalty for wrong answers. The girl luckily sits in the middle of two geniuses, so she is going to cheat.

However, the geniuses have limitations. Each of them may or may not know the answers to some questions. Anyway, it is safe to assume that the answers on their answer sheets are absolutely correct.

To make sure she will not get caught by the proctor, the girl will glance at most p times, each time looking at no more than k consecutive questions on one of the two geniuses' answer sheet. When the girl looks at some question on an answer sheet, she copies the answer to that question if it is on that answer sheet, or does nothing otherwise.

Help the girl find the maximum number of questions she can get correct.

泽恩和泽恩的暗恋对象刚刚决定开始约会！然而，这位女孩正在为她的物理期末考试发愁，需要你的帮助。

共有 $n$ 道题目，编号从 $1$ 到 $n$。第 $i$ 题位于第 $i+1$ 题之前（$1 \le i < n$）。由于答错将受到极重的扣分惩罚，因此每道题都不能靠猜测作答。幸运的是，这位女孩恰好坐在两位天才中间，因此她打算抄袭。

不过，这两位天才也有局限性：每人可能知道其中某些题目的答案，也可能不知道。但可以安全地假设，他们答题卡上的答案绝对正确。

为了确保不被监考老师发现，这位女孩最多只会偷看 $p$ 次；每次偷看时，她至多连续查看某一位天才答题卡上的 $k$ 道题目。当女孩查看某位天才答题卡上的某道题目时，若该题答案出现在该答题卡上，她便抄下答案；否则不做任何操作。

请帮这位女孩计算她最多能答对多少道题。

The first line contains three integers n, p, and k (1 ≤ n, p ≤ 1, 000, 1 ≤ k ≤ min(n, 50)) — the number of questions, the maximum number of times the girl can glance, and the maximum number of consecutive questions that can be looked at in one time glancing, respectively.

The second line starts with one integer r (0 ≤ r ≤ n), denoting the number of questions the first genius has answered on his answer sheet. Then follow r integers _a_1, _a_2, ..., a__r (1 ≤ a__i ≤ n) — the answered questions, given in a strictly-increasing order (that is, a__i < a__i + 1).

The third line starts with one integer s (0 ≤ s ≤ n), denoting the number of questions the second genius has answered on his answer sheet. Then follow s integers _b_1, _b_2, ..., b__s (1 ≤ b__i ≤ n) — the answered questions, given in a strictly-increasing order (that is, b__i < b__i + 1).

第一行包含三个整数 $n$、$p$ 和 $k$（$1 ≤ n, p ≤ 1{,}000$，$1 ≤ k ≤ \min(n, 50)$），分别表示题目总数、该女生最多可偷看的次数，以及每次偷看时最多可连续查看的题目数量。

第二行以一个整数 $r$（$0 ≤ r ≤ n$）开头，表示第一位天才在其答题纸上已作答的题目数量；随后是 $r$ 个整数 $a_1, a_2, ..., a_r$（$1 ≤ a_i ≤ n$），表示已作答的题目编号，且严格递增（即 $a_i < a_{i+1}$）。

第三行以一个整数 $s$（$0 ≤ s ≤ n$）开头，表示第二位天才在其答题纸上已作答的题目数量；随后是 $s$ 个整数 $b_1, b_2, ..., b_s$（$1 ≤ b_i ≤ n$），表示已作答的题目编号，且严格递增（即 $b_i < b_{i+1}$）。

Print one integer — the maximum number of questions the girl can answer correctly.

输出一个整数——女孩最多能正确回答的问题数量。

Let (x, l, r) denote the action of looking at all questions i such that l ≤ i ≤ r on the answer sheet of the x-th genius.

In the first sample, the girl could get 4 questions correct by performing sequence of actions (1, 1, 3) and (2, 5, 6).

In the second sample, the girl could perform sequence of actions (1, 3, 5), (2, 2, 4), and (2, 6, 8) to get 7 questions correct.

用 $(x,\,l,\,r)$ 表示查看第 $x$ 位天才的答题纸上所有满足 $l\le i\le r$ 的题目 $i$ 的操作。

在第一个样例中，该女生可通过执行操作序列 $(1,\,1,\,3)$ 和 $(2,\,5,\,6)$ 答对 4 道题。

在第二个样例中，该女生可通过执行操作序列 $(1,\,3,\,5)$、$(2,\,2,\,4)$ 和 $(2,\,6,\,8)$ 答对 7 道题。