Night Market

Taro is going to a summer festival.

Along the road to the festival there are $N$ night-market stalls, numbered $1$ through $N$ in order. For each stall, the fun you gain by playing there and the time it takes to play are both integers. Playing at stall $i$ gives $A_i$ fun and takes $B_i$ time.

As the highlight of the festival there is a fireworks show, and the largest firework goes up at time $S$. Taro really wants to watch this largest firework.

To enjoy both the stalls and the firework, Taro plans his schedule from the moment he arrives, time $0$, until the festival ends at time $T$.

Taro chooses $k$ stalls $(1 \le k \le N)$ and picks an integer visiting time for each. He cannot choose the same stall twice. Let the chosen stall numbers in increasing order be $y_1, y_2, \dots, y_k$, and let $x_{y_i}$ be the time he visits stall $y_i$; then Taro plays at stall $y_i$ from time $x_{y_i}$ to time $x_{y_i} + B_{y_i}$.

Taro plays at the stalls in increasing order of their numbers and cannot play at two stalls at the same time. The time to move between stalls is negligible.

Once time passes $T$ the festival ends, so he cannot play at any stall after that. Also, while he is playing at a stall he cannot watch the firework. However, if time $S$ is exactly the moment he starts or finishes playing at some stall, then Taro can still watch that firework.

That is, the plan must satisfy all of the following conditions.

• $y_1 < y_2 < \dots < y_k$
• $x_{y_1}, x_{y_2}, \dots, x_{y_k}$ are integers.
• $0 \le x_{y_1} < x_{y_1} + B_{y_1} \le x_{y_2} < x_{y_2} + B_{y_2} \le \dots \le x_{y_k} < x_{y_k} + B_{y_k} \le T$
• There is no $i$ such that $x_{y_i} < S < x_{y_i} + B_{y_i}$.

Let $M$ be the sum of the fun values $A_{y_1}, A_{y_2}, \dots, A_{y_k}$ of the chosen stalls. Taro wants to make $M$ as large as possible.

Given the information of the $N$ stalls and the times $S$ and $T$, write a program that finds the maximum possible value of $M$.

The following is given on standard input.

The first line contains three integers $N$, $T$, $S$ separated by spaces: the number of stalls is $N$, the festival ends at time $T$, and the largest firework goes up at time $S$.

Each of the next $N$ lines describes one stall. Line $i + 1$ $(1 \le i \le N)$ contains two integers $A_i$ and $B_i$ separated by a space: playing at stall $i$ gives $A_i$ fun and takes $B_i$ time.

It is guaranteed that at least one valid plan exists for every input.

Print the maximum value of $M$ as a single integer on one line.

• $1 \le N \le 3000$ — the number of stalls
• $1 \le T \le 3000$ — the time the festival ends
• $0 \le S \le T$ — the time the largest firework goes up
• $0 \le A_i \le 100000$ — the fun gained by playing at stall $i$
• $1 \le B_i \le 3000$ — the time it takes to play at stall $i$

In the first example, the following plan maximizes $M$.

• Visit stall $1$ at time $0$ and play from time $0$ to time $9$.
• Visit stall $2$ at time $9$ and play from time $9$ to time $13$.
• Visit stall $4$ at time $14$ and play from time $14$ to time $17$.

The firework goes up at time $S = 14$, which is exactly when Taro starts playing at stall $4$, so he can still watch it. Here $M = 8 + 2 + 6 = 16$.