밤 노점 (Night Market)

태로는 여름 축제에 놀러 가기로 했다.

축제가 열리는 장소로 가는 길에는 밤 노점이 $N$개 늘어서 있다. 각 노점에는 $1$부터 $N$까지 번호가 차례로 매겨져 있으며, 노점에서 놀 때 얻는 즐거움과 노는 데 걸리는 시간이 각각 정수로 정해져 있다. 노점 $i$에서 놀 때 얻는 즐거움은 $A_i$이고, 노는 데 걸리는 시간은 $B_i$이다.

축제의 하이라이트로 불꽃놀이가 있는데, 시각 $S$에 가장 큰 불꽃이 터진다. 태로는 이 가장 큰 불꽃을 꼭 보고 싶어 한다.

태로는 노점과 불꽃을 모두 즐기기 위해, 축제에 도착하는 시각 $0$부터 축제가 끝나는 시각 $T$까지의 일정을 세우려고 한다.

태로는 노점 중에서 $k$개 $(1 \le k \le N)$를 골라 각각 방문할 시각을 정수로 정한다. 같은 노점을 두 번 고를 수는 없다. 고른 노점의 번호를 작은 순서대로 $y_1, y_2, \dots, y_k$라 하고, 노점 $y_i$를 방문하는 시각을 $x_{y_i}$라 하면, 태로는 노점 $y_i$에서 시각 $x_{y_i}$부터 시각 $x_{y_i} + B_{y_i}$까지 논다.

태로는 노점 번호가 작은 순서대로 놀며, 두 노점에서 동시에 놀 수는 없다. 노점 사이를 이동하는 데 걸리는 시간은 무시할 수 있다.

시각 $T$를 넘기면 축제가 끝나므로 노점에서 놀 수 없다. 또한 노점에서 노는 동안에는 불꽃을 볼 수 없다. 다만 시각 $S$가 어떤 노점에서 놀기 시작하는 시각이거나 놀이를 끝내는 시각과 정확히 같다면, 태로는 그 불꽃을 볼 수 있다.

즉, 일정은 다음 조건을 모두 만족해야 한다.

• $y_1 < y_2 < \dots < y_k$
• $x_{y_1}, x_{y_2}, \dots, x_{y_k}$는 정수이다.
• $$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$$
• $x_{y_i} < S < x_{y_i} + B_{y_i}$를 만족하는 $i$는 존재하지 않는다.

고른 노점의 즐거움 $A_{y_1}, A_{y_2}, \dots, A_{y_k}$의 합을 $M$이라 하자. 태로는 $M$이 가능한 한 커지도록 일정을 세우고 싶다.

$N$개 노점의 정보와 시각 $S$, $T$가 주어질 때, $M$의 최댓값을 구하는 프로그램을 작성하여라.

표준 입력으로 다음 정보가 주어진다.

첫째 줄에는 정수 $N$, $T$, $S$가 공백으로 구분되어 주어진다. 이는 노점의 수가 $N$개, 축제가 끝나는 시각이 $T$, 가장 큰 불꽃이 터지는 시각이 $S$임을 뜻한다.

이어지는 $N$개의 줄에는 노점의 정보가 주어진다. $i + 1$번째 줄 $(1 \le i \le N)$에는 정수 $A_i$, $B_i$가 공백으로 구분되어 주어지며, 이는 노점 $i$에서 놀 때 얻는 즐거움이 $A_i$, 노는 데 걸리는 시간이 $B_i$임을 뜻한다.

모든 입력에 대해, 하나 이상의 일정을 세울 수 있음이 보장된다.

표준 출력으로 $M$의 최댓값을 나타내는 정수 하나를 한 줄에 출력한다.

• $1 \le N \le 3000$ — 노점의 수
• $1 \le T \le 3000$ — 축제가 끝나는 시각
• $0 \le S \le T$ — 가장 큰 불꽃이 터지는 시각
• $0 \le A_i \le 100000$ — 노점 $i$에서 놀 때 얻는 즐거움
• $1 \le B_i \le 3000$ — 노점 $i$에서 노는 데 걸리는 시간

첫 번째 예제에서는 다음과 같이 일정을 세우면 $M$을 최대로 만들 수 있다.

• 노점 $1$을 시각 $0$에 방문하여 시각 $0$부터 $9$까지 논다.
• 노점 $2$를 시각 $9$에 방문하여 시각 $9$부터 $13$까지 논다.
• 노점 $4$를 시각 $14$에 방문하여 시각 $14$부터 $17$까지 논다.

불꽃은 시각 $S = 14$에 터지는데, 이 시각은 노점 $4$에서 놀기 시작하는 시각과 정확히 같으므로 태로는 불꽃을 볼 수 있다. 이때 $M = 8 + 2 + 6 = 16$이다.