Exam Cheating
Contest: Codeforces Round 408 (Div. 2)
Difficulty rating: 2400
Tags: binary search, dp

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.

Input format:
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 a1, a2, ..., ar (1 ≤ ai ≤ n) — the answered questions, given in a strictly-increasing order (that is, ai < ai + 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 b1, b2, ..., bs (1 ≤ bi ≤ n) — the answered questions, given in a strictly-increasing order (that is, bi < bi + 1).

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
6 2 3
3 1 3 6
4 1 2 5 6

Example output:
4

Example input:
8 3 3
4 1 3 5 6
5 2 4 6 7 8

Example output:
7

Editorial:
This problem can be solved using dynamic programming.
First, observe that it is never suboptimal to look as many consecutive questions as possible. That is, just look k consecutive questions whenever you decide to glance, unless it exceeds the corner (question n).
Let dp[i][j][a][b] denote the number of questions you can get correct by considering questions 1 to i by glancing exactly j times with a and b being the number of remaining questions that can be looked at as a benefit of the previous glances. As stated before, it is optimal to look as many consecutive questions as possible, so when we decide to look, we share this benefit (of looking) to the next questions too, and it are stored in a and b, which denote how many of the next consecutive questions can be looked without paying one more glance. The answer can be calculated in O(npk2). (You can see in the code as to how.)
However, npk2 can be up to (1000) * (1000) * (50) * (50)  =  2, 500, 000, 000, so the solution will not fit in the time limit of 2 seconds.
This can be improved. Observe that if p > 2 * ceil(n / k), you can look at all questions on both geniuses’ answer sheets, so the answer can be found in O(n) (or you can just set p to 2 * ceil(n / k) and run the dynamic programming). By eliminating this case, the running time for dynamic programming will become O(npk2) = O(n(n / k)k2) = O(n2k). This, indeed, will fit in time, as n2k is only (1000) * (1000) * (50)  =  50, 000, 000.
Problem with memory limit might still persist, so you will need to optimize the use of memory. For example, since you need only dp[i - 1][..][..][..] and dp[i][..][..][..] when calculating dp[i][..][..][..], you could remember only the two last rows. The memory use will be much smaller. The use of short data type (instead of int) may also help.
Please see the commented code for more details.