32691번 - 팀 구성

문제

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)$

출력

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

제한

힌트