Maximizing Contest Difficulty Sum

In this problem, you are given a sequence of problems, each with a positive length and a difficulty value. The problems are arranged in chronological order. You wish to form one or more contests for an informatics competition. Each contest consists of a contiguous segment of the problems, and the following conditions must be satisfied:

• The total length of the selected segment (i.e. the sum of the lengths of the problems) must be between \(L\) and \(H\) (inclusive). That is, if a segment covers indices \(i\) to \(j\), and \(S = a_i+a_{i+1}+\cdots+a_j\), then \(L \le S \le H\).
• For any two contests chosen, their sets of problems must not have a subset relation. In other words, if one contest uses the problems from indices \(i\) to \(j\) and another uses indices \(k\) to \(l\), then it is forbidden that one segment is completely contained in the other. Formally, if \(i \le k\) then it must be that \(j < l\) (and similarly, if \(k \le i\) then \(l < j\)).

The difficulty of a contest is defined as the sum of the difficulties of its problems. A problem may be used in different contests. Your task is to select a set of contests (i.e. contiguous segments satisfying the length condition) that meet the above non‐containment constraint and maximize the total sum of difficulties over all contests.

Note: Two contests \([i,j]\) and \([k,l]\) can be present together if when sorted by their starting index the corresponding end indices are in strict increasing order, i.e. if \(i<k\) then \(j<l\). This ensures that neither contest is a subset of the other.

inputFormat

The input is given as follows:

1. The first line contains three integers: \(n\) (the number of problems), \(L\) and \(H\) (the minimum and maximum allowed total length for a contest, respectively).
2. The following \(n\) lines each contain two positive integers: the length \(a_i\) and the difficulty \(b_i\) of the \(i\)th problem.

You may assume that all numbers are positive and that \(L \le H\).

outputFormat

Output a single integer, the maximum total difficulty sum over a set of contests selected under the given constraints. If no valid contest can be formed, output 0.

sample

5 5 8
2 3
3 4
1 2
4 5
2 1

24