Exam Cheating

题意翻译

muronglin是个学渣，考试的时候，她一道题也不会做 她的左右桌分别是学霸chhokmah和学霸lukelin，虽然学霸并不是题题都会做，但他们做了的题一定都对 现在muronglin想要作弊，但是为了不被监考员抓住，她最多偷看p次，一次能看连续的k道题 给定n和la和lb，分别为题目总数，chhokmah做出题目数和lukelin做出题目数，再给出两位学霸做出题目序列，问muronglin最多能偷看到几道题的答案

题目描述

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&lt;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.

输入输出格式

输入格式

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}&lt;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}&lt;b_{i+1} $ ).

输出格式

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

输入输出样例

输入样例 #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

说明

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.