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]。
在第二个示例中,您必须将矮盒子放在高盒子下面。