Wardrobe
Contest: VK Cup 2018 - Round 2
Difficulty rating: 2700
Tags: dp, greedy

Olya wants to buy a custom wardrobe. It should have n boxes with heights a1, a2, ..., an, stacked one on another in some order. In other words, we can represent each box as a vertical segment of length ai, and all these segments should form a single segment from 0 to $$\sum_{i=1}^{n} a_i$$ without any overlaps.

Some of the boxes are important (in this case bi = 1), others are not (then bi = 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 format:
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 a1, a2, ..., an (1 ≤ ai ≤ 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 b1, b2, ..., bn (0 ≤ bi ≤ 1), where bi equals 1 if the i-th box is important, and 0 otherwise.

Output format:
Print a single integer — the maximum possible convenience of the wardrobe.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
5 3 6
3 2 5 1 2
1 1 0 1 0

Example output:
2

Example input:
2 2 5
3 6
1 1

Example output:
1

Editorial:
The first idea of the author's solution is to reverse the problem: change l to H - r and r to H - l, where H is the total height of the wardrobe. Now an important box is counted in the answer if and only if its top edge is within the segment [l, r]. We'll see later the profit of this operation.
Now, we'll build a wardrobe of arbitrary height using only a subset of the boxes, and choose the maximum possible answer. Why can we remove the constraint to use all boxes? We can always assume that we add all the boxes we don't take at the top of the boxes we take, and the answer won't decrease. So, we can do some kind of knapsack, where not taking a box means putting it on the top after considering all boxes.
What we don't know is how to compute the answer and in which order to consider the boxes in the knapsack. Ok, if we consider them in such an order that there is an optimal answer in which the boxes we "take" in the knapsack always come in this order, then computing the answer is easy: we can always assume that we put a new box on the top of already taken ones, and add 1 to the current answer if it is an important box and its top edge falls in the range [l, r].
Now we should find such an order. Note that in an optimal answer we can always arrange boxes in this order: some number of unimportant boxes, then some number of important boxes that don't increase the answer, then some number of important boxes that increase the answer, and after that a mix of important and unimportant boxes which don't count in the answer and that we consider as "not taken" in the knapsack. This means that we can first consider all unimportant boxes in the knapsack, and then all important ones. It's also easy to see that the order of unimportant boxes does not matter. However, it turns out that the order of important boxes matters.
To choose the order of important boxes, we can use an old, but good trick. Suppose two important boxes with heights ai and aj stand one on the other. Answer the question: "What is the condition such that if it is satisfied, then it is always better to put aj on the top of ai, and not vice versa?" Here we consider only the boxes that count in the answer and those under them, because other we simply "don't take" in the knapsack. It turns out that the condition is simple: aj ≤ ai, no matter do these boxes count in the answer or not. Here we used the fact that we inversed the problem, and the position of the top edge matters, not the bottom one. So, as we now know that it is always optimal to put the important boxes from largest to smallest (in the inversed problem), we can sort them in that order and perform the knapsack.
The complexity is $${\mathcal{O}}(n\cdot\sum a_{i})$$. This can also be reduced to $${\cal O}(H\sqrt{H})$$ where H is the height of the wardrobe, using a standard optimization for the knapsack.