전시장

전시장에서 그림을 판매하는 업체에 전시대 하나가 배정된다. 전시할 그림들은 모두 직사각형이며 폭은 같고, 높이는 그림마다 다를 수 있다. 각 그림에는 가격이 정해져 있다.

전시대의 폭은 그림의 폭과 같으므로, 여러 그림을 전시하려면 앞뒤로 겹치도록 배치해야 한다. 관람객은 전시대를 정면에서 바라보며, 어떤 그림의 보이는 세로 길이는 그 그림이 앞쪽 그림들에 가려지지 않고 드러난 부분의 세로 길이이다.

위 그림처럼 그림들을 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

판매 가능한 그림들의 가격 합이 최대가 되도록 배치했을 때의 최대 합을 첫째 줄에 출력한다.