{"problem":{"name":"E. Wardrobe","description":{"content":"Olya wants to buy a custom wardrobe. It should have _n_ boxes with heights _a_1, _a_2, ..., _a__n_, stacked one on another in some order. In other words, we can represent each box as a vertical segmen","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF924E"},"statements":[{"statement_type":"Markdown","content":"Olya wants to buy a custom wardrobe. It should have _n_ boxes with heights _a_1, _a_2, ..., _a__n_, stacked one on another in some order. In other words, we can represent each box as a vertical segment of length _a__i_, and all these segments should form a single segment from 0 to without any overlaps.\n\nSome of the boxes are important (in this case _b__i_ = 1), others are not (then _b__i_ = 0). Olya defines the _convenience_ of the wardrobe as the number of important boxes such that their bottom edge is located between the heights _l_ and _r_, inclusive.\n\nYou are given information about heights of the boxes and their importance. Compute the maximum possible convenience of the wardrobe if you can reorder the boxes arbitrarily.\n\n## Input\n\nThe first line contains three integers _n_, _l_ and _r_ (1 ≤ _n_ ≤ 10 000, 0 ≤ _l_ ≤ _r_ ≤ 10 000) — the number of boxes, the lowest and the highest heights for a bottom edge of an important box to be counted in convenience.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 10 000) — the heights of the boxes. It is guaranteed that the sum of height of all boxes (i. e. the height of the wardrobe) does not exceed 10 000: Olya is not very tall and will not be able to reach any higher.\n\nThe second line contains _n_ integers _b_1, _b_2, ..., _b__n_ (0 ≤ _b__i_ ≤ 1), where _b__i_ equals 1 if the _i_\\-th box is important, and 0 otherwise.\n\n## Output\n\nPrint a single integer — the maximum possible convenience of the wardrobe.\n\n[samples]\n\n## Note\n\nIn the first example you can, for example, first put an unimportant box of height 2, then put an important boxes of sizes 1, 3 and 2, in this order, and then the remaining unimportant boxes. The convenience is equal to 2, because the bottom edges of important boxes of sizes 3 and 2 fall into the range \\[3, 6\\].\n\nIn the second example you have to put the short box under the tall box.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Olya 想要购买一个定制衣柜。它应包含 #cf_span[n] 个盒子，高度分别为 #cf_span[a1, a2, ..., an]，这些盒子以某种顺序堆叠在一起。换句话说，我们可以将每个盒子表示为长度为 #cf_span[ai] 的垂直线段，所有这些线段应拼接成一个从 #cf_span[0] 到 #cf_span[\\sum a_i] 的连续线段，且无重叠。\n\n某些盒子是重要的（此时 #cf_span[bi = 1]），其余不是（此时 #cf_span[bi = 0]）。Olya 将衣柜的 _便利性_ 定义为：底部边缘高度位于区间 #cf_span[l] 到 #cf_span[r]（含端点）之间的重要盒子的数量。\n\n给定盒子的高度及其重要性信息，请计算在可以任意重新排列盒子顺序的情况下，衣柜可能达到的最大便利性。\n\n第一行包含三个整数 #cf_span[n], #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 10 000], #cf_span[0 ≤ l ≤ r ≤ 10 000]）——分别表示盒子数量、重要盒子底部边缘高度的最小值和最大值（只有在此范围内才计入便利性）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10 000]）——表示每个盒子的高度。保证所有盒子高度之和（即衣柜总高度）不超过 #cf_span[10 000]：Olya 身高有限，无法够到更高的位置。\n\n第三行包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn]（#cf_span[0 ≤ bi ≤ 1]），其中 #cf_span[bi] 等于 #cf_span[1] 表示第 #cf_span[i] 个盒子是重要的，等于 #cf_span[0] 表示不是重要的。\n\n请输出一个整数——衣柜可能达到的最大便利性。\n\n在第一个例子中，你可以先放一个高度为 #cf_span[2] 的非重要盒子，然后按顺序放置高度为 #cf_span[1]、#cf_span[3] 和 #cf_span[2] 的重要盒子，最后放置剩余的非重要盒子。便利性为 #cf_span[2]，因为高度为 #cf_span[3] 和 #cf_span[2] 的重要盒子的底部边缘分别位于高度 #cf_span[2] 和 #cf_span[5]，均落在区间 #cf_span[[3, 6]] 内。\n\n在第二个例子中，你必须将矮盒子放在高盒子下方。\n\n## Input\n\n第一行包含三个整数 #cf_span[n], #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 10 000], #cf_span[0 ≤ l ≤ r ≤ 10 000]）——分别表示盒子数量、重要盒子底部边缘高度的最小值和最大值（只有在此范围内才计入便利性）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10 000]）——表示每个盒子的高度。保证所有盒子高度之和（即衣柜总高度）不超过 #cf_span[10 000]：Olya 身高有限，无法够到更高的位置。第三行包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn]（#cf_span[0 ≤ bi ≤ 1]），其中 #cf_span[bi] 等于 #cf_span[1] 表示第 #cf_span[i] 个盒子是重要的，等于 #cf_span[0] 表示不是重要的。\n\n## Output\n\n请输出一个整数——衣柜可能达到的最大便利性。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以先放一个高度为 #cf_span[2] 的非重要盒子，然后按顺序放置高度为 #cf_span[1]、#cf_span[3] 和 #cf_span[2] 的重要盒子，最后放置剩余的非重要盒子。便利性为 #cf_span[2]，因为高度为 #cf_span[3] 和 #cf_span[2] 的重要盒子的底部边缘分别位于高度 #cf_span[2] 和 #cf_span[5]，均落在区间 #cf_span[[3, 6]] 内。在第二个例子中，你必须将矮盒子放在高盒子下方。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ n $ be the number of boxes.\n- Let $ a_i \\in \\mathbb{Z}^+ $ be the height of box $ i $, for $ i = 1, 2, \\dots, n $.\n- Let $ b_i \\in \\{0, 1\\} $ indicate whether box $ i $ is important ($ b_i = 1 $) or not ($ b_i = 0 $).\n- Let $ l, r \\in \\mathbb{Z}_{\\geq 0} $ with $ l \\leq r $ define the height range $ [l, r] $ for bottom edges of important boxes to contribute to convenience.\n- The wardrobe is formed by stacking all boxes vertically in some order. The bottom edge of the first box is at height 0. The bottom edge of the $ k $-th box in the stack is at height equal to the sum of heights of all boxes below it.\n\n**Constraints:**\n\n- The total height $ H = \\sum_{i=1}^n a_i \\leq 10{,}000 $.\n- Boxes can be reordered arbitrarily.\n\n**Objective:**\n\nMaximize the number of important boxes (i.e., $ b_i = 1 $) whose bottom edge lies in the interval $ [l, r] $.\n\n---\n\n**Formal Problem Statement:**\n\nLet $ \\pi $ be a permutation of $ \\{1, 2, \\dots, n\\} $, representing the order of boxes from bottom to top.\n\nDefine the bottom height of box $ \\pi(k) $ as:\n\n$$\ns_k = \\sum_{j=1}^{k-1} a_{\\pi(j)}\n$$\n\nLet $ I = \\{ i \\in \\{1, \\dots, n\\} \\mid b_i = 1 \\} $ be the set of important boxes.\n\nDefine the convenience of permutation $ \\pi $ as:\n\n$$\nC(\\pi) = \\left| \\left\\{ i \\in I \\mid l \\leq s_{\\pi^{-1}(i)} \\leq r \\right\\} \\right|\n$$\n\n**Goal:**\n\n$$\n\\max_{\\pi \\in S_n} C(\\pi)\n$$\n\n--- \n\n**Note:** The problem reduces to selecting a subset of important boxes to place such that their bottom edges fall in $ [l, r] $, while arranging all boxes (important and unimportant) in an order that maximizes this count, subject to the cumulative height constraint.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF924E","tags":["dp","greedy"],"sample_group":[["5 3 6\n3 2 5 1 2\n1 1 0 1 0","2"],["2 2 5\n3 6\n1 1","1"]],"created_at":"2026-03-03 11:00:39"}}