팀 구성

시간 제한1초메모리 제한1024 MB

요약

각 구성원의 실력과 목표 순위가 주어질 때, 순위 차이가 K 이하인 서로 겹치지 않는 3명 조를 골라 실력 합이 최대가 되도록 구하는 문제입니다.

난이도: 보통10점 중 6점
유형: 정렬, 동적 계획법, 슬라이딩 윈도우
정답자: 아직 제출이 없습니다

문제

DPS 부원들의 ICPC 참여를 독려하려고 참여 희망자 공지를 올린 도훈이는, 아직 팀이 정해지지 않은 부원들을 3명씩 한 팀으로 묶으려고 한다. 팀 구성을 신청한 부원은 1번부터 $N$ 번까지 총 $N$ 명이다. $i$ 번 부원의 프로그래밍 실력은 $A_i$ 이고, 목표 등수는 $B_i$ 등이다.

각 팀의 최상의 결과를 위해 도훈이는 다음 조건을 만족하도록 팀을 구성한다.

하나의 팀은 3명으로 구성되어야 한다.
같은 부원이 여러 팀에 동시에 속하면 안 된다.
팀에 속한 세 명의 가장 높은 목표 등수와 가장 낮은 목표 등수의 차이는 $K$ 이하여야 한다.
모든 부원이 팀에 속해 있을 필요는 없다.

각 팀의 팀 실력은 팀에 속한 세 부원의 프로그래밍 실력의 합이다. 도훈이는 팀 실력의 합이 최대가 되도록 팀을 구성하려고 한다. 조건에 맞게 팀을 구성했을 때 팀 실력의 합의 최댓값을 구하라.

입력

첫째 줄에 팀 구성을 신청한 부원의 수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. ( $3 \le N \le 200000$ , $0 \le K \le 10^9$ )

다음 $N$ 개의 줄에 $i$ 번 부원의 프로그래밍 실력 $A_i$ 와 목표 등수 $B_i$ 가 공백으로 구분되어 주어진다. ( $1 \le A_i, B_i \le 10^9$ )

출력

조건에 맞게 팀을 구성했을 때, 팀 실력의 합의 최댓값을 출력한다.

예제2

예제 1
입력
```
4 4
10 10
20 16
16 11
13 13
```
예상 출력
```
39
```
예제 2
입력
```
6 10
1 1
2 1
3 1
4 1
5 1
6 1
```
예상 출력
```
21
```