← 返回题目列表

Codeforces · 924/E

E. 衣柜

中文机器翻译题面 查看原题

Olya 想购买一个定制衣柜。它应该有 n 个高度为 a1, a2, ..., an 的盒子,按某种顺序堆叠在一起。换句话说,我们可以将每个盒子表示为长度为 ai 的垂直线段,并且所有这些线段应形成从 0 到 $$\sum_{i=1}^{n} a_i$$ 的单个线段,没有任何重叠。

有些框很重要(在本例中bi = 1),其他框则不重要(则bi = 0)。 Olya 将衣柜的便利性定义为重要盒子的数量,其底边位于高度 l 和 r 之间(含)。

您将获得有关方框高度及其重要性的信息。如果您可以任意重新排列盒子,请计算衣柜的最大可能便利性。

输入

第一行包含三个整数 n、l 和 r (1 ≤ n ≤ 10 000, 0 ≤ l ≤ r ≤ 10 000) — 盒子的数量、重要盒子底部边缘的最低和最高高度,以方便计数。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 10 000) – 盒子的高度。保证所有盒子的高度总和(即衣柜的高度)不超过 10 000:Olya 不是很高,无法达到更高的高度。

第二行包含 n 个整数 b1, b2, ..., bn (0 ≤ bi ≤ 1),其中如果第 i 个框很重要,则 bi 等于 1,否则为 0。

输出

打印一个整数——衣柜的最大可能便利性。

示例

输入 #1

5 3 6
3 2 5 1 2
1 1 0 1 0

输出 #1

2

输入 #2

2 2 5
3 6
1 1

输出 #2

1

注意

在第一个示例中,例如,您可以首先放置一个高度为 2 的不重要框,然后按此顺序放置一个尺寸为 1、3 和 2 的重要框,然后再放置其余的不重要框。便利性等于 2,因为尺寸为 3 和 2 的重要框的底边落入范围 [3, 6]。

在第二个示例中,您必须将矮盒子放在高盒子下面。