USACO 2014 Mar Bronze- 보석 탐사 > 문제은행 : 정보올림피아드&알고리즘




2705 : 보석 탐사

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
57 회   
시도횟수
261 회   

문제

광산 업자인 왕보석은 최근 쥬얼랜드에서 보석이 매장된 지역을 발견하였다. 그 지역에 대하여 1제곱미터를 기준(이를 섹터라 하자.)으로 나누어 탐사를 마친 후 살펴보니 보석이 있는 곳들은 마치 일차원배열처럼 길게 일렬로 늘어서 있었다.


탐사된 모든 보석을 채굴하면 좋겠지만 쥬얼랜드에서는 무분별한 보석 채굴을 방지하기 위하여 신청자가 어떤 섹터 S를 선택하면 S섹터를 기준으로 S-K섹터로부터 S+K섹터까지 범위에서만 채굴을 허락한다고 한다. 또한 모든 섹터의 채굴 비용은 동일하나 얻을 수 있는 수익은 다를 수 있다고 한다. 따라서 왕보석은 본격적인 채굴에 앞서 수익성을 따져 보고자 한다. 현재 탐사자료를 기초로 허락된 범위에서 얻을 수 있는 가장 큰 수익은 얼마일까?이를 구하는 프로그램을 작성하시오.


입력형식

첫 행에 보석이 발견된 섹터의 수 N ( 1 ≤ N ≤ 100,000)과 허락된 범위 K ( 1 ≤ K ≤ 2,000,000)가 주어진다.
다음 N개의 행에는 보석이 발견된 곳의 정보가 입력되는데, 얻을 수 있는 수익 Vi ( 1 ≤ Vi ≤10,000)와 위치 Pi( 0 ≤ Pi ≤ 1,000,000)가 공백으로 구분되어 주어진다.


출력형식

탐사자료를 기초로 허락된 범위에서 얻을 수 있는 가장 큰 수익을 출력한다.


입력 예

4 3
4 7
10 15
2 2
5 1

출력 예

11

Hint!

왕보석이 섹터 4를 선택하면 섹터 1, 2, 7에서 채굴할 수 있게 되며 수익은 11이 된다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP