전시장
시간 제한1초메모리 제한256 MB
폭이 같고 높이가 다른 그림들을 앞뒤로 쌓을 때 보이는 세로 길이가 S 이상인 그림들의 가격 합이 최대가 되도록 배치하는 문제입니다.
문제
전시장에서 그림을 판매하는 업체에 전시대 하나가 배정된다. 전시할 그림들은 모두 직사각형이며 폭은 같고, 높이는 그림마다 다를 수 있다. 각 그림에는 가격이 정해져 있다.
전시대의 폭은 그림의 폭과 같으므로, 여러 그림을 전시하려면 앞뒤로 겹치도록 배치해야 한다. 관람객은 전시대를 정면에서 바라보며, 어떤 그림의 보이는 세로 길이는 그 그림이 앞쪽 그림들에 가려지지 않고 드러난 부분의 세로 길이이다.
위 그림처럼 그림들을 C, B, A, D 순서로 앞에서부터 뒤로 겹쳐 놓으면, 앞쪽의 그림 B가 그림 A를 완전히 가릴 수 있다. 이 경우 그림 A는 관람객에게 전혀 보이지 않고, 일부라도 보이는 그림만 관심 대상이 된다.
보이는 세로 길이가 정수 S 이상인 그림만 관람객이 관심을 보이고 구매한다고 하자. 이런 그림을 판매 가능한 그림이라고 부른다.
각 그림의 높이와 가격이 주어질 때, 그림을 적절한 순서로 배치하여 판매 가능한 그림들의 가격 합을 최대화하려고 한다. 얻을 수 있는 최대 가격 합을 구하시오.
입력
첫째 줄에 그림의 개수 N과 판매 가능한 그림을 판단하는 정수 S가 공백으로 구분되어 주어진다.
다음 N개의 줄에는 각 그림의 높이 H와 가격 C가 공백으로 구분되어 주어진다.
제한은 다음과 같다.
- 1 <= N <= 300,000
- 1 <= S <= H <= 20,000,000
- 1 <= C <= 1,000
출력
판매 가능한 그림들의 가격 합이 최대가 되도록 배치했을 때의 최대 합을 첫째 줄에 출력한다.