{"raw_statement":[{"iden":"statement","content":"Stepan is a very experienced olympiad participant. He has _n_ cups for Physics olympiads and _m_ cups for Informatics olympiads. Each cup is characterized by two parameters — its significance _c__i_ and width _w__i_.\n\nStepan decided to expose some of his cups on a shelf with width _d_ in such a way, that:\n\n*   there is at least one Physics cup and at least one Informatics cup on the shelf,\n*   the total width of the exposed cups does not exceed _d_,\n*   from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance _x_ is exposed, then all the cups for this subject with significance greater than _x_ must be exposed too).\n\nYour task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width _d_, considering all the rules described above. The total significance is the sum of significances of all the exposed cups."},{"iden":"input","content":"The first line contains three integers _n_, _m_ and _d_ (1 ≤ _n_, _m_ ≤ 100 000, 1 ≤ _d_ ≤ 109) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.\n\nEach of the following _n_ lines contains two integers _c__i_ and _w__i_ (1 ≤ _c__i_, _w__i_ ≤ 109) — significance and width of the _i_\\-th cup for Physics olympiads.\n\nEach of the following _m_ lines contains two integers _c__j_ and _w__j_ (1 ≤ _c__j_, _w__j_ ≤ 109) — significance and width of the _j_\\-th cup for Informatics olympiads."},{"iden":"output","content":"Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width _d_, considering all the rules described in the statement.\n\nIf there is no way to expose cups on the shelf, then print 0."},{"iden":"examples","content":"Input\n\n3 1 8\n4 2\n5 5\n4 2\n3 2\n\nOutput\n\n8\n\nInput\n\n4 3 12\n3 4\n2 4\n3 5\n3 4\n3 5\n5 2\n3 4\n\nOutput\n\n11\n\nInput\n\n2 2 2\n5 3\n6 3\n4 2\n8 1\n\nOutput\n\n0"},{"iden":"note","content":"In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2, so after Stepan exposes it, the width of free space on the shelf becomes equal to 6. Also, Stepan must expose the second Physics cup (which has width 5), because it is the most significant cup for Physics (its significance equals 5). After that Stepan can not expose more cups on the shelf, because there is no enough free space. Thus, the maximum total significance of exposed cups equals to 8."}],"translated_statement":[{"iden":"statement","content":"Stepan 是一位经验丰富的竞赛选手。他拥有 #cf_span[n] 个物理竞赛奖杯和 #cf_span[m] 个信息学竞赛奖杯。每个奖杯由两个参数描述：其重要性 #cf_span[ci] 和宽度 #cf_span[wi]。\n\nStepan 决定将部分奖杯摆放在宽度为 #cf_span[d] 的架子上，满足以下条件：\n\n你的任务是确定在满足上述所有规则的前提下，Stepan 在宽度为 #cf_span[d] 的架子上摆放奖杯所能获得的最大总重要性。总重要性是所有被摆放奖杯的重要性的总和。\n\n第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[d]（#cf_span[1 ≤ n, m ≤ 100 000]，#cf_span[1 ≤ d ≤ 10^9]）——分别表示物理竞赛奖杯的数量、信息学竞赛奖杯的数量和架子的宽度。\n\n接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[ci] 和 #cf_span[wi]（#cf_span[1 ≤ ci, wi ≤ 10^9]）——表示第 #cf_span[i] 个物理竞赛奖杯的重要性和宽度。\n\n接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[cj] 和 #cf_span[wj]（#cf_span[1 ≤ cj, wj ≤ 10^9]）——表示第 #cf_span[j] 个信息学竞赛奖杯的重要性和宽度。\n\n请输出在满足题目所述所有规则的前提下，Stepan 在宽度为 #cf_span[d] 的架子上摆放奖杯所能获得的最大总重要性。\n\n如果没有可行的摆放方式，请输出 #cf_span[0]。\n\n在第一个例子中，Stepan 只有一个信息学奖杯，必须摆放在架子上。它的重要性为 #cf_span[3]，宽度为 #cf_span[2]，因此摆放后架子剩余空间为 #cf_span[6]。同时，Stepan 必须摆放第二个物理奖杯（宽度为 #cf_span[5]），因为它是物理奖杯中重要性最高的（重要性为 #cf_span[5]）。摆放后，剩余空间不足，无法再摆放更多奖杯。因此，被摆放奖杯的最大总重要性为 #cf_span[8]。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[d]（#cf_span[1 ≤ n, m ≤ 100 000]，#cf_span[1 ≤ d ≤ 10^9]）——分别表示物理竞赛奖杯的数量、信息学竞赛奖杯的数量和架子的宽度。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[ci] 和 #cf_span[wi]（#cf_span[1 ≤ ci, wi ≤ 10^9]）——表示第 #cf_span[i] 个物理竞赛奖杯的重要性和宽度。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[cj] 和 #cf_span[wj]（#cf_span[1 ≤ cj, wj ≤ 10^9]）——表示第 #cf_span[j] 个信息学竞赛奖杯的重要性和宽度。"},{"iden":"output","content":"请输出在满足题目所述所有规则的前提下，Stepan 在宽度为 #cf_span[d] 的架子上摆放奖杯所能获得的最大总重要性。如果没有可行的摆放方式，请输出 #cf_span[0]。"},{"iden":"examples","content":"输入\n3 1 8\n4 2\n5 5\n4 2\n3 2\n输出\n8\n\n输入\n4 3 12\n3 4\n2 4\n3 5\n3 4\n3 5\n5 2\n3 4\n输出\n11\n\n输入\n2 2 2\n5 3\n6 3\n4 2\n8 1\n输出\n0"},{"iden":"note","content":"在第一个例子中，Stepan 只有一个信息学奖杯，必须摆放在架子上。它的重要性为 #cf_span[3]，宽度为 #cf_span[2]，因此摆放后架子剩余空间为 #cf_span[6]。同时，Stepan 必须摆放第二个物理奖杯（宽度为 #cf_span[5]），因为它是物理奖杯中重要性最高的（重要性为 #cf_span[5]）。摆放后，剩余空间不足，无法再摆放更多奖杯。因此，被摆放奖杯的最大总重要性为 #cf_span[8]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ P = \\{(c_i, w_i)\\}_{i=1}^n $ be the set of Physics cups, where $ c_i $ is significance and $ w_i $ is width.\n- Let $ I = \\{(c_j, w_j)\\}_{j=1}^m $ be the set of Informatics cups.\n- Let $ d $ be the total shelf width.\n\n**Constraints:**\n\n- Exactly **one** Informatics cup must be selected.\n- At least **one** Physics cup must be selected.\n- The sum of widths of all selected cups must not exceed $ d $.\n\n**Objective:**\n\nMaximize the total significance of selected cups:\n\n$$\n\\max_{\\substack{j \\in [1,m] \\\\ S \\subseteq P, S \\neq \\emptyset \\\\ w_j + \\sum_{i \\in S} w_i \\leq d}} \\left( c_j + \\sum_{i \\in S} c_i \\right)\n$$\n\n**Equivalently:**\n\nFor each Informatics cup $ j $, let $ r = d - w_j $. If $ r < \\min_{i} w_i $, skip. Otherwise, select a non-empty subset $ S \\subseteq P $ with total width $ \\leq r $ that maximizes $ \\sum_{i \\in S} c_i $. Then take the maximum over all valid $ j $.\n\nLet $ f(r) = \\max \\left\\{ \\sum_{i \\in S} c_i \\mid S \\subseteq P, S \\neq \\emptyset, \\sum_{i \\in S} w_i \\leq r \\right\\} $.\n\nThen the answer is:\n\n$$\n\\max_{\\substack{j=1 \\\\ w_j \\leq d}}^m \\left( c_j + f(d - w_j) \\right)\n$$\n\nIf no valid selection exists, return $ 0 $.","simple_statement":null,"has_page_source":false}