{"raw_statement":[{"iden":"statement","content":"Dr. Doofenshmirtz did something to the space-time continuum.\n\nNow there are one billion days, one billion locks, and one billion keys. This is the type of thing that only happens in cartoons and math problems!!\n\n1,000,000,000 days of summer vacation and school comes along just to end it! For the rest of summer vacation, Dr. Doofenshmirtz will occasionally be doing things to take over the Greater Tri-State Area and Perry the Platypus has to stop him.\n\nThe good news is that Agent P has managed to make an imprint of a set of keys and duplicate all of them. The bad news is that each day, Perry will be locked inside a different room with a different lock. And the set of keys he has might not have a correct key to open the lock on some days.\n\nThere are a total of 1,000,000,000 different locks, one for each day of summer vacation, and there are 1,000,000,000 different keys. As before, each key can open a lock if the difference between their numbers is exactly one. To be more explicit:\n\nYou will be given the set of keys that Perry the Platypus has as well as the lock numbers on the days that Dr. Doofenshmirtz will be active.\n\nOutput how many days Perry can successfully stop the mad doctor.\n\nEach test case consists of four lines.\n\nThe first line contains an integer $k$, the number of keys that Perry has.\n\nThe second line contains $k$ space-separated integers representing each key $k_i$.\n\nThe third line contains an integer $L$, the number of locks.\n\nThe fourth line contains $L$ space-separated integers, representing each lock $L_i$.\n\n*Constraints*\n\n$1 <= k <= 10^5$ \n\n$1 <= k_i <= 10^9$ \n\n$1 <= L <= 10^5$ \n\n$1 <= L_i <= 10^9$ \n\nNo two $k_i$s are the same. \n\nNo two $L_i$s are the same. \n\nOutput a single integer, the number of days that Perry can successfully stop Dr. Doofenshmirtz.\n\n"},{"iden":"input","content":"Each test case consists of four lines.The first line contains an integer $k$, the number of keys that Perry has.The second line contains $k$ space-separated integers representing each key $k_i$.The third line contains an integer $L$, the number of locks.The fourth line contains $L$ space-separated integers, representing each lock $L_i$.*Constraints*$1 <= k <= 10^5$ $1 <= k_i <= 10^9$ $1 <= L <= 10^5$ $1 <= L_i <= 10^9$ No two $k_i$s are the same. No two $L_i$s are the same. "},{"iden":"output","content":"Output a single integer, the number of days that Perry can successfully stop Dr. Doofenshmirtz."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of qualities.  \nLet $ g \\in \\mathbb{R}^+ $ be Kouhai’s growth rate limit.  \nLet $ W = (W_1, \\dots, W_q) \\in \\mathbb{R}^q $ be the weight vector for qualities.  \nLet $ F = (F_1, \\dots, F_q) \\in \\mathbb{R}^q $ be Senpai’s change rate factors.  \nLet $ C = (C_1, \\dots, C_q) \\in \\mathbb{R}^q $ be Senpai’s constant factors.  \n\nLet $ S_i(t) = F_i t + C_i $ for $ i \\in \\{1, \\dots, q\\} $.  \nLet $ P_i(t) : \\mathbb{R}_{\\geq 0} \\to \\mathbb{R} $ be continuously differentiable functions with $ P_i(0) = 0 $ for all $ i $.  \n\n**Constraints**  \n1. $ \\sum_{i=1}^{q} \\left( \\frac{d}{dt} P_i(t) \\right)^2 \\leq g^2 $ for all $ t \\geq 0 $.  \n2. $ P_i(0) = 0 $ for all $ i \\in \\{1, \\dots, q\\} $.  \n\n**Objective**  \nFind the minimal $ t \\geq 0 $ such that there exist functions $ P_i(t) $ satisfying the constraints and:  \n$$\n\\sum_{i=1}^{q} S_i(t) \\leq \\sum_{i=1}^{q} W_i P_i(t)\n$$  \ni.e.,  \n$$\n\\sum_{i=1}^{q} (F_i t + C_i) \\leq \\sum_{i=1}^{q} W_i P_i(t)\n$$","simple_statement":"Find the earliest time $ t \\geq 0 $ such that, by optimally growing your qualities $ P_i(t) $ with a total growth rate limit $ g $, your weighted sum $ \\sum P_i(t) \\cdot W_i $ is at least Senpai’s weighted sum $ \\sum (F_i \\cdot t + C_i) $.","has_page_source":false}