Maximum Energy Journey

You are given a journey divided into n segments. Initially you have f units of fuel and e units of energy. For each segment i (1-indexed), if you decide to traverse it, you must spend f_i units of fuel and you will gain e_i units of energy. Alternatively, you may choose to skip the segment, carrying your current fuel and energy to the next segment.

The challenge is to determine the maximum total energy you can have by the end of the journey, while never running out of fuel when attempting a segment.

The problem can be formulated using dynamic programming. Define a function \(dp[i][j]\) as the maximum energy achievable after considering the first \(i\) segments with \(j\) units of fuel remaining. The transitions are as follows:

• If you skip segment \(i+1\): \(dp[i+1][j] = \max(dp[i+1][j], dp[i][j])\).
• If you take segment \(i+1\) and \(j \geq f_{i+1}\): \(dp[i+1][j - f_{i+1}] = \max(dp[i+1][j - f_{i+1}], dp[i][j] + e_{i+1})\).

Print the maximum energy obtainable after processing all segments.

inputFormat

The input is given via standard input (stdin) in the following format:

n f e
f_1 e_1
f_2 e_2
... 
 f_n e_n

Where:

• n is the number of segments.
• f is the initial fuel.
• e is the initial energy.
• Each of the next n lines contains two integers: f_i (fuel consumption for segment i) and e_i (energy gain for segment i).

outputFormat

Output a single integer which is the maximum energy obtainable by the end of the journey. The output should be printed to standard output (stdout).

## sample

5 10 0
2 5
3 7
4 3
5 8
2 6

21