Description

As Little Tiger solves more and more problems, he can now act as a little teacher and often helps teachers create problems for the informatics olympiad class to use for practice. Making problems is indeed a troublesome task. Now there is an even more troublesome situation:

Little Tiger has collected a large number of problems and arranged them in a sequence in the order they were collected. Each problem has its own statement length and difficulty. Little Tiger wants to use these problems to create many contests. However, there are requirements:

• The problems in the same contest must form a contiguous segment of this sequence, and the number of problems is unrestricted.
• The total statement length must not exceed $H$ and must not be less than $L$.
• It is not allowed to have two contests such that all problems of one contest also appear in the other. (In other words, the problem sets of different contests must not have a containment or be-contained relationship.)

Problems may be reused across different contests.

Now, Little Tiger wants to know, under the above constraints, what is the maximum possible total difficulty over all contests? (Define the difficulty of a contest as the sum of the difficulties of all problems appearing in that contest.)

Input Format

The first line contains three integers $N$, $L$, and $H$.

The second line contains $N$ integers. The $i$-th integer $a_i$ denotes the statement length of the $i$-th problem.

The third line contains $N$ integers. The $i$-th integer $b_i$ denotes the difficulty of the $i$-th problem.

Output Format

Output a single integer: the maximum total difficulty over all contests.

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

21

注：样例中，3场，第一场选1，2两题，第二场选3，4两题，第三场选4，5，6三题。

Hint

For $40\%$ of the testdata, $1 \le N \le 100$.

For $100\%$ of the testdata, $1 \le N \le 1000$, $0 \le a_i, b_i \le 10^5$.

Translated by ChatGPT 5