题目描述

佳佳得到的这些树枝在属性上完全相同。每一个树枝都有 $\red{n }$段（用 $\red{1\sim n }$编号），给定了 每段的长度 $\red{L[i]}$和每段的魔力值 $\red{M[i]}$。单独的一段是不可以从中间切开的，你可以做的就是 选择一段或连续的几段，把它们作为一个整体切下来，再用来制作魔杖。但是一根魔杖的长 度不能太长——不能大于给定的值 $\red{hi}$；也不能太短——不能小于给定的值 $\red{lo}$。

魔杖有一个奇怪的要求：如果某一根魔杖的制作材料是另一根魔杖的一部分，则这两根 魔杖之间将发生冲突。比如说树枝有三段，从左到右的长度分别为 $\red{4}$、$\red{1}$、$\red{3，}$佳佳需要长度 为 $\red{4 }$到 $\red{5 }$之间的魔杖。佳佳可以用一根树枝的前两段做出一个长度为 $\red{5 }$的魔杖，用一根树枝 的后两段做出长度为 $\red{4 }$的魔杖；但他决不能用一根树枝的前两段做了魔杖后再单独使用另一 根树枝的第一段做成魔杖，因为前者包含了后者的所有成分，这会导致冲突。

我们假设佳佳可以得到任意多这样的树枝。佳佳需要制作出若干个互不冲突的魔杖，使 所有魔杖的魔力值之和最大。（魔杖的长度就是组成它的那些段的长度的总和，魔力值亦然）。

输入格式

第一行有三个用空格隔开的正整数，分别表示 $\red{n}$、$\red{lo}$、$\red{hi}$。

第二行的 $\red{n }$个用空格隔开的正整数就是 $\red{L[1]}$、$\red{L[2],...,L[n]}$。

第三行的 $\red{n }$个用空格隔开的正整数就是 $\red{M[1]}$、$\red{M[2],...,M[n]}$。

输入文件以一个回车$\red{/}$换行符结尾。

输出格式

只用输出一个整数，表示能够获得的魔力值的最大值。

样例

输入样例

6 4 5
1 3 3 2 2 1
2 3 1 4 5 2

输出样例

21

提示

样例说明：

取$\red{[1 ~3] [3 ~2] [2 ~2 ~1]}$做成魔杖。

得到最大权值 $\red{2+3+1+4+4+5+2=21}$。

数据范围：

对于 $\red{30\%}$的数据，$\red{n<=10}$；

对于 $\red{50\%}$的数据，$\red{n<=100}$；

对于 $\red{100\%}$的数据，$\red{n<=1000，}$$\red{lo<=hi<=2^31-1，}$$\red{L[i],M[i]<=100 000}$