전시회 2
시간 제한1초메모리 제한1024 MB
N개의 그림 중 D 이상 떨어진 M개를 골라 선택된 그림들의 최솟값을 최대화하고, 불가능하면 -1을 출력한다.
문제
JOI 미술관에는 동서 방향으로 곧게 뻗은 복도에 N개의 그림이 걸려 있고, 1부터 N까지 번호가 붙어 있다. 그림 i(1 ≦ i ≦ N)는 복도의 서쪽 끝에서 Xi미터 위치에 걸려 있으며, 그 가치는 Vi이다.
이 미술관에서는 내일부터 "에고이 전"이 열릴 예정이고, 매우 많은 관람객이 올 것으로 예상된다. "에고이 전"에서는 M개의 그림을 전시할 예정이다.
두 그림이 가까운 위치에 전시되면 보기 어려우므로, 다음 조건을 만족하도록 N-M개의 그림을 떼어내고 복도에 M개의 그림만 남기기로 했다.
- 어떤 두 그림에 대해서도 위치가
D미터 이상 떨어져 있어야 한다.
전시된 M개의 그림 가치의 최솟값을 "에고이 전"의 화려함이라고 한다. 복도에 남길 M개의 그림을 잘 선택해서 "에고이 전"의 화려함을 최대한 크게 하고 싶다.
N개의 그림 정보와 복도에 남길 그림의 개수가 주어졌을 때, 조건을 만족하는 그림을 남기는 방법이 존재하는지 판정하고, 존재하면 "에고이 전"의 화려함의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
N M D
X1 V1
X2 V2
:
XN VN
출력
조건을 만족하는 그림을 남기는 방법이 존재하지 않으면, 표준 출력에 -1을 1행으로 출력한다.
조건을 만족하는 그림을 남기는 방법이 존재하면, 표준 출력에 "에고이 전"의 화려함의 최댓값을 1행으로 출력한다.
제한
1 ≦ N ≦ 100 000.1 ≦ M ≦ N.1 ≦ D ≦ 1 000 000 000.1 ≦ Xi ≦ 1 000 000 000(1 ≦ i ≦ N).Xi ≠ Xj(1 ≦ i < j ≦ N).1 ≦ Vi ≦ 1 000 000 000(1 ≦ i ≦ N).- 입력되는 값은 모두 정수이다.