팀 구성

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

요약

실력 A와 목표 등수 B를 가진 N명의 부원을 목표 등수 최댓값과 최솟값의 차이가 K 이하인 3인 팀으로 묶어 실력 합의 최댓값을 구한다.

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

문제

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

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

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

각 팀의 팀 실력은 해당 팀에 속한 세 부원들의 프로그래밍 실력의 합이며, 도훈이는 팀 실력의 합이 최대가 되도록 팀들을 구성하고자 한다. 도훈이를 위해, 조건에 맞게 팀을 구성할 때 팀 실력의 합의 최댓값을 구해주자.

입력

첫째 줄에 팀 구성을 신청한 부원의 수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. $(3\le N\le 200\\,000;$ $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
```