Team Formation

Time limit1sMemory limit1024 MB

Summary

Given N members with skill and target rank, pick disjoint triples whose rank spread is at most K to maximize the total skill of the chosen triples.

Level: Medium6 of 10
Topics: Sorting, Dynamic programming, Sliding window
Solved: No attempts yet

Problem

DoHun posted a notice to encourage DPS members to join ICPC and wants to group the members who do not have a team yet into teams of 3. There are $N$ members numbered 1 to $N$ . Member $i$ has programming skill $A_i$ and target rank $B_i$ .

To get the best results, DoHun forms teams that satisfy the following conditions.

Each team must have exactly 3 members.
A member cannot belong to more than one team.
In a team, the difference between the highest target rank and the lowest target rank among its three members must be at most $K$ .
Not every member has to be on a team.

The team skill of a team is the sum of the programming skills of its three members. DoHun wants the total team skill to be as large as possible. Find the maximum possible total team skill when the teams are formed under these conditions.

Input

The first line contains the number of members $N$ and $K$ , separated by a space. ( $3 \le N \le 200000$ , $0 \le K \le 10^9$ )

The next $N$ lines each contain the programming skill $A_i$ and the target rank $B_i$ of member $i$ , separated by a space. ( $1 \le A_i, B_i \le 10^9$ )

Output

Print the maximum total team skill when the teams are formed under the conditions.

Examples2

Example 1
Input
```
4 4
10 10
20 16
16 11
13 13
```
Expected output
```
39
```
Example 2
Input
```
6 10
1 1
2 1
3 1
4 1
5 1
6 1
```
Expected output
```
21
```