English · Original
Chinese · Translation
Formal · Original
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.
Some 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.
You 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.
## Input
The 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.
The 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.
The 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.
## Output
Print a single integer — the maximum possible convenience of the wardrobe.
[samples]
## Note
In 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\].
In the second example you have to put the short box under the tall box.
Olya 想要购买一个定制衣柜。它应包含 #cf_span[n] 个盒子，高度分别为 #cf_span[a1, a2, ..., an]，这些盒子以某种顺序堆叠在一起。换句话说，我们可以将每个盒子表示为长度为 #cf_span[ai] 的垂直线段，所有这些线段应拼接成一个从 #cf_span[0] 到 #cf_span[\sum a_i] 的连续线段，且无重叠。
某些盒子是重要的（此时 #cf_span[bi = 1]），其余不是（此时 #cf_span[bi = 0]）。Olya 将衣柜的 _便利性_ 定义为：底部边缘高度位于区间 #cf_span[l] 到 #cf_span[r]（含端点）之间的重要盒子的数量。
给定盒子的高度及其重要性信息，请计算在可以任意重新排列盒子顺序的情况下，衣柜可能达到的最大便利性。
第一行包含三个整数 #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] 表示不是重要的。
请输出一个整数——衣柜可能达到的最大便利性。
在第一个例子中，你可以先放一个高度为 #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]] 内。
在第二个例子中，你必须将矮盒子放在高盒子下方。
## Input
第一行包含三个整数 #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] 表示不是重要的。
## Output
请输出一个整数——衣柜可能达到的最大便利性。
[samples]
## Note
在第一个例子中，你可以先放一个高度为 #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]] 内。在第二个例子中，你必须将矮盒子放在高盒子下方。
**Definitions:**
- Let $ n $ be the number of boxes.
- Let $ a_i \in \mathbb{Z}^+ $ be the height of box $ i $, for $ i = 1, 2, \dots, n $.
- Let $ b_i \in \{0, 1\} $ indicate whether box $ i $ is important ($ b_i = 1 $) or not ($ b_i = 0 $).
- 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.
- 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.
**Constraints:**
- The total height $ H = \sum_{i=1}^n a_i \leq 10{,}000 $.
- Boxes can be reordered arbitrarily.
**Objective:**
Maximize the number of important boxes (i.e., $ b_i = 1 $) whose bottom edge lies in the interval $ [l, r] $.
---
**Formal Problem Statement:**
Let $ \pi $ be a permutation of $ \{1, 2, \dots, n\} $, representing the order of boxes from bottom to top.
Define the bottom height of box $ \pi(k) $ as:
$$
s_k = \sum_{j=1}^{k-1} a_{\pi(j)}
$$
Let $ I = \{ i \in \{1, \dots, n\} \mid b_i = 1 \} $ be the set of important boxes.
Define the convenience of permutation $ \pi $ as:
$$
C(\pi) = \left| \left\{ i \in I \mid l \leq s_{\pi^{-1}(i)} \leq r \right\} \right|
$$
**Goal:**
$$
\max_{\pi \in S_n} C(\pi)
$$
---
**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.
API Response (JSON)
{
"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 segmen...",
"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_...",
"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 im...",
"is_translate": false,
"language": "Formal"
}
]
}