P1584 Wand

On a spring outing, Smart accidentally obtained something good — some very precious branches. These branches can be used to make high-quality wands. Choosing how to cut to make the wands is crucial. The key is: a wand can be neither too long nor too short, and the wands produced must not conflict. The branches Smart obtained are identical in their properties. Each branch has $n$ segments (numbered from $1$ to $n$). The length $l$ and the magic value $m$ of each segment are given. You may choose one segment or a consecutive block of segments, cut them off as a whole, and use that as a wand. However, the length of a wand must not be too long — it must not exceed $h$; and it must not be too short — it must not be less than $low$. In other words, the length must be between $low$ and $h$ inclusive. There is a strange rule for wands: if the material used for one wand is a part of the material used for another wand, then these two wands conflict. For example, suppose a branch has three segments, and from left to right their lengths are $4$, $1$, $3$. Smart needs wands with lengths between $4$ and $5$. He can use the first two segments of a branch to make a wand of length $5$, and use the last two segments to make a wand of length $4$; but he must never use the first two segments to make a wand and then separately use only the first segment of another branch to make a wand, because the former contains all the components of the latter, which would cause a conflict. Assume Smart has access to an unlimited number of such branches. Smart needs to produce several pairwise non-conflicting wands so that the sum of the magic values of all wands is maximized. (The length of a wand is the sum of the lengths of the segments that form it, and its magic value is the sum of the magic values likewise.)

The first line contains three integers separated by spaces, representing $n$, $low$, and $h$. The second line contains $n$ integers separated by spaces; the $i$-th integer is $l_i$. The third line contains $n$ integers separated by spaces; the $i$-th integer is $m_i$.

Output a single integer on one line, the maximum total magic value that can be obtained.

#### Explanation for Sample Input/Output 1 Choose $[1\ 3]$ $[3\ 2]$ $[2\ 2\ 1]$ to make wands, obtaining the maximum total weight $2+3+1+4+4+5+2=21$。 --- #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $1 \le n \le 1000$, $1 \le low \le h < 2^{31}$. - $1 \le l_i, m_i \le 10^5$. Translated by ChatGPT 5