{"problem":{"name":"E. Exam Cheating","description":{"content":"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_ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF796E"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThere 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.\n\n<center>![image](https://espresso.codeforces.com/981ca34c65bbb14c13f06866a09f10b311b5e4c5.png)</center>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.\n\nTo 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.\n\nHelp the girl find the maximum number of questions she can get correct.\n\n## Input\n\nThe 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.\n\nThe 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).\n\nThe 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\n## Output\n\nPrint one integer — the maximum number of questions the girl can answer correctly.\n\n[samples]\n\n## Note\n\nLet (_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.\n\nIn the first sample, the girl could get 4 questions correct by performing sequence of actions (1, 1, 3) and (2, 5, 6).\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Zane 和他的暗恋对象刚刚开始约会！然而，女孩在物理期末考试中遇到了问题，需要你的帮助。\n\n共有 #cf_span[n] 道题目，编号从 #cf_span[1] 到 #cf_span[n]。题目 #cf_span[i] 出现在题目 #cf_span[i + 1] 之前（#cf_span[1 ≤ i < n]）。由于答错题惩罚严重，这些题目无法靠猜测作答。幸运的是，女孩坐在两位天才之间，因此她打算作弊。\n\n然而，这两位天才有局限性：他们可能知道也可能不知道某些题目的答案。无论如何，可以安全地假设他们答卷上的答案是绝对正确的。\n\n为了确保不被监考老师发现，女孩最多只能偷看 #cf_span[p] 次，每次偷看时最多查看其中一位天才答卷上的 #cf_span[k] 道连续题目。当女孩偷看某道题目时，如果该题的答案在该天才的答卷上，她就会抄写该答案；否则什么也不做。\n\n请帮助女孩找出她能答对的最多题目数量。\n\n第一行包含三个整数 #cf_span[n], #cf_span[p], 和 #cf_span[k]（#cf_span[1 ≤ n, p ≤ 1, 000], #cf_span[1 ≤ k ≤ min(n, 50)]）—— 分别表示题目数量、女孩最多偷看次数、以及每次偷看最多可查看的连续题目数。\n\n第二行以一个整数 #cf_span[r]（#cf_span[0 ≤ r ≤ n]）开头，表示第一位天才在答卷上作答的题目数量。接着是 #cf_span[r] 个整数 #cf_span[a1, a2, ..., ar]（#cf_span[1 ≤ ai ≤ n]）—— 表示他作答的题目，按严格递增顺序给出（即 #cf_span[ai < ai + 1]）。\n\n第三行以一个整数 #cf_span[s]（#cf_span[0 ≤ s ≤ n]）开头，表示第二位天才在答卷上作答的题目数量。接着是 #cf_span[s] 个整数 #cf_span[b1, b2, ..., bs]（#cf_span[1 ≤ bi ≤ n]）—— 表示他作答的题目，按严格递增顺序给出（即 #cf_span[bi < bi + 1]）。\n\n请输出一个整数——女孩能答对的最多题目数量。\n\n令 #cf_span[(x, l, r)] 表示查看第 #cf_span[x] 位天才答卷上所有满足 #cf_span[l ≤ i ≤ r] 的题目 #cf_span[i] 的操作。\n\n在第一个样例中，女孩可以通过执行操作序列 #cf_span[(1, 1, 3)] 和 #cf_span[(2, 5, 6)] 得到 #cf_span[4] 道题正确。\n\n在第二个样例中，女孩可以通过执行操作序列 #cf_span[(1, 3, 5)], #cf_span[(2, 2, 4)] 和 #cf_span[(2, 6, 8)] 得到 #cf_span[7] 道题正确。\n\n## Input\n\n第一行包含三个整数 #cf_span[n], #cf_span[p], 和 #cf_span[k]（#cf_span[1 ≤ n, p ≤ 1, 000], #cf_span[1 ≤ k ≤ min(n, 50)]）—— 分别表示题目数量、女孩最多偷看次数、以及每次偷看最多可查看的连续题目数。第二行以一个整数 #cf_span[r]（#cf_span[0 ≤ r ≤ n]）开头，表示第一位天才在答卷上作答的题目数量。接着是 #cf_span[r] 个整数 #cf_span[a1, a2, ..., ar]（#cf_span[1 ≤ ai ≤ n]）—— 表示他作答的题目，按严格递增顺序给出（即 #cf_span[ai < ai + 1]）。第三行以一个整数 #cf_span[s]（#cf_span[0 ≤ s ≤ n]）开头，表示第二位天才在答卷上作答的题目数量。接着是 #cf_span[s] 个整数 #cf_span[b1, b2, ..., bs]（#cf_span[1 ≤ bi ≤ n]）—— 表示他作答的题目，按严格递增顺序给出（即 #cf_span[bi < bi + 1]）。\n\n## Output\n\n请输出一个整数——女孩能答对的最多题目数量。\n\n[samples]\n\n## Note\n\n令 #cf_span[(x, l, r)] 表示查看第 #cf_span[x] 位天才答卷上所有满足 #cf_span[l ≤ i ≤ r] 的题目 #cf_span[i] 的操作。\n\n在第一个样例中，女孩可以通过执行操作序列 #cf_span[(1, 1, 3)] 和 #cf_span[(2, 5, 6)] 得到 #cf_span[4] 道题正确。\n\n在第二个样例中，女孩可以通过执行操作序列 #cf_span[(1, 3, 5)], #cf_span[(2, 2, 4)] 和 #cf_span[(2, 6, 8)] 得到 #cf_span[7] 道题正确。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, p, k \\in \\mathbb{Z}^+ $ denote the number of questions, maximum glances, and maximum consecutive questions per glance, respectively.  \nLet $ A \\subseteq \\{1, 2, \\dots, n\\} $ be the set of questions answered correctly by genius 1.  \nLet $ B \\subseteq \\{1, 2, \\dots, n\\} $ be the set of questions answered correctly by genius 2.  \n\n**Constraints**  \n1. $ 1 \\leq n, p \\leq 1000 $  \n2. $ 1 \\leq k \\leq \\min(n, 50) $  \n3. $ A $ and $ B $ are given as strictly increasing sequences of distinct integers from $ \\{1, \\dots, n\\} $.  \n4. The girl may perform at most $ p $ glances.  \n5. Each glance covers at most $ k $ consecutive questions on *one* genius’s sheet.  \n\n**Objective**  \nMaximize the number of distinct questions $ i \\in \\{1, \\dots, n\\} $ such that $ i \\in A \\cup B $, and $ i $ is covered by at least one glance interval of length at most $ k $, using at most $ p $ such intervals (each confined to either $ A $ or $ B $).  \n\nFormally, find the maximum size of $ \\bigcup_{j=1}^m I_j \\cap (A \\cup B) $, where:  \n- $ m \\leq p $,  \n- Each $ I_j = [l_j, r_j] \\subseteq \\{1, \\dots, n\\} $ with $ r_j - l_j + 1 \\leq k $,  \n- For each $ j $, $ I_j $ is entirely within the domain of either $ A $ or $ B $ (i.e., if $ I_j $ is used to cover $ A $, then $ I_j \\subseteq \\{1, \\dots, n\\} $, but only elements in $ A \\cap I_j $ count; similarly for $ B $).  \n\nEquivalently, select at most $ p $ intervals of length $ \\leq k $ (each assigned to either $ A $ or $ B $) to maximize the total number of covered elements in $ A \\cup B $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF796E","tags":["binary search","dp"],"sample_group":[["6 2 3\n3 1 3 6\n4 1 2 5 6","4"],["8 3 3\n4 1 3 5 6\n5 2 4 6 7 8","7"]],"created_at":"2026-03-03 11:00:39"}}