Magical Wand Crafting

Smart has unexpectedly obtained a very precious branch during his spring outing. This branch can be used to craft a high‐quality magical wand! Each branch consists of n segments, numbered from 1 to n. For each segment i, you are given its length \(l_i\) and magic value \(m_i\).

You may choose a contiguous block of one or more segments from a branch and cut it off to craft a wand. The wand's total length \(L\) is the sum of the lengths of its segments, i.e., \(L = \sum_{i=a}^{b} l_i\) for some contiguous interval \([a,b]\). To be acceptable, the wand must satisfy:

• \(L \geq low\)
• \(L \leq h\)

There is, however, a quirky restriction: if the material used for one wand is a contiguous subset of the material used for another wand from the same branch, a conflict occurs. For example, if a branch has three segments with lengths 4, 1, 3 (in order) and Smart needs a wand with length in the range [4, 5], one may craft a wand from the first two segments (length 4+1 = 5) and also craft a wand from the last two segments (length 1+3 = 4) from different branches. However, one cannot craft a wand from the first two segments on one branch and then craft another wand from just the first segment from the same branch, because the latter is completely contained in the former.

Assume that Smart can obtain arbitrarily many identical branches. However, from each branch, you may cut exactly one contiguous segment to craft a wand (to avoid any conflict within the same branch). Smart's goal is to maximize the total magic value of the wands he crafts. The magic value of a wand is the sum of the magic values of the segments used, i.e., \(\sum_{i=a}^{b} m_i\) for the chosen block from a branch.

Note: Since branches are unlimited and wand crafting from different branches does not cause conflict, the problem reduces to finding the maximum magic value obtainable from a single branch by choosing one contiguous segment whose total length \(L = \sum_{i=a}^{b} l_i\) satisfies \(low \leq L \leq h\). If no valid segment exists, the answer is 0.

inputFormat

The first line contains three integers: n (number of segments), low and h (minimum and maximum allowed wand length).

Then, there are n lines. The i-th line contains two integers l and m, denoting the length and magic value of segment i respectively.

outputFormat

Output a single integer – the maximum total magic value obtainable by crafting one wand (i.e. by selecting one contiguous block of segments whose total length is between low and h). If no valid wand can be crafted, output 0.

sample

3 4 5
4 4
1 1
3 3

5