문제 번호 6213 --야시장(夜店)

6213: 야시장(夜店)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 0  해결 문제 수: 0
[제출][채점상황][게시판][:]

문제 설명

 타로 군은 JOI 신사에서 열리는 여름 축제에 가려고 한다.

 JOI 신사까지 가는 길의 야시장에는 N개의 노점이 있다. 각각의 노점에는 순서대로 1부터 N까지의 번호가 붙어있으며, 각 노점에는 ‘재미있는 정도’와 ‘머무를 수 있는 시간’이 각각 정수로 정해져있다. 노점 i에서 놀 때, 재미있는 정도는 Ai, 머무를 수 있는 시간은 Bi이다.

 또한 여름 축제에는 메인 이벤트로 불꽃 놀이가 열리며, 그 중에서도 시간 S에 가장 큰 불꽃이 발사된다고 한다. 타로 군은 가장 큰 불꽃이 꼭 보고 싶다. 타로 군은 야시장과 불꽃 놀이를 모두 만끽하기 위해, 축제 장소에 도착하는 시간을 0으로 하고 축제가 끝나는 시간 T 까지의 계획을 세우기로 하였다.

 타로 군은 야시장에서 k개(1 ≤ k ≤ N)의 노점을 선택하고, 각 노점에 방문할 시각을 정수로 결정한다. 같은  노점에는 두 번 이상 방문하지 않는다. 선정한 노점을 번호가 작은 것 부터 순서대로 y1, y2, …, yk라고 하고, 노점 yi에서 놀기 시작한 시각을 Xyi이라고 한다. 노점 yi에서 나오는 시각은 Xyi + Bi가 된다. (역주 : 노점에서 나오는 시각 = 노점에 방문한 시점의 시각 + 노는 데 걸리는 시간)

 타로 군은 노점을 번호의 오름차순으로 방문하며, 동시에 두 개의 노점에서 놀 수는 없다. 또한 노점 사이의 이동 시간은 무시할 수 있다.

 시간 T를 초과하게 되면 여름 축제가 끝나기 때문에 더 이상 야시장에서 놀 수 없다. 또한 노점에서 놀고 있는 동안에는 불꽃 놀이를 볼 수 없다. 시간 S가 노점에서 놀기 시작한 시간과 끝나는 시간 사이에 있을 경우에만 타로 군이 불꽃 놀이를 볼 수 있는 것으로 한다.

 

 지금까지의 조건을 정리하면 다음과 같다.

  • y1 < y2 < … < yk
  • Xy1, Xy2, …, Xyk 는 정수
  • 0 ≤ Xy1 < Xy1 + By1 ≤ Xy2 < Xy2 + By2 ≤ … ≤ Xyk < Xyk + Byk ≤ T
  • Xyi < S < Xyi + Byi 인 상황이 존재해서는 안된다.


 선택한 노점의 재미잇는 정도의 총 합을 M이라고 한다. 타로 군은 M이 가능한 커지도록 계획을 세우려고 한다. N개의 노점에 대한 정보와 S, T의 값이 주어졌을 때 얻을 수 있는 M의 최댓값을 구하는 프로그램을 작성하라.

입력

 입력 데이터는 아래와 같이 이루어져있다.

 첫 번째 줄에는 세 개의 정수 N(노점의 수), T(축제가 끝나는 시각), S(가장 큰 불꽃을 발사하는 시간)가 띄어쓰기로 구분되어 주어진다. 

 이어지는 N개의 줄에는 노점의 정보가 주어진다. i + 1번 째 줄(1 ≤ i ≤ N)에는 두 정수 Ai(노점이 재미있는 정도), Bi(노점에 머무를 수 있는 시간)가 띄어쓰기로 구분되어 주어진다.

 모든 입력에 대해서 한 종류 이상의 계획을 세울 수 있음이 보장된다.


 데이터의 범위는 다음과 같다.

  • 1 ≤ N ≤ 3,000
  • 1 ≤ T ≤ 3,000
  • 0 ≤ S ≤ T
  • 0 ≤ Ai ≤ 100,000
  • 1 ≤ Bi ≤ 3,000

출력

 M의 최댓값을 하나의 정수로 출력하라.

입력예시

5 20 14
8 9
2 4
7 13
6 3
5 8

출력예시

16

도움말

 입출력 예시에 대한 풀이는 다음과 같다.



 노점 1을 시각 0 ~ 9에 방문한다. (재미도 : 8)


 노점 2을 시각 9 ~ 14에 방문한다. (재미도 : 8 + 2)


 시각 14에 불꽃 놀이를 구경한다.


 노점 4를 시각 14 ~ 17에 방문한다. (재미도 8 + 2 + 6)


 더 이상 방문할 수 있는 노점이 없다.



출처

[제출][채점상황]