Party

Time limit2sMemory limit1024 MB

Summary

Pair up girls with different personality types so each pair's happiness sum is at most k, maximizing the total happiness of all paired girls.

Level: Medium7 of 10
Topics: Sorting, Two pointers, Greedy
Solved: No attempts yet

Problem

$n$ cherry blossom girls held a party. At this party, they will form dating relationships. A dating relationship is formed between two cherry blossom girls, and each girl can belong to at most one dating relationship.

Each girl has a personality type $a_i$ and a happiness value $b_i$ . For two girls $i$ and $j$ to form a dating relationship, their personality types must be different ( $a_i \neq a_j$ ), and the sum of their happiness values must be at most $k$ ( $b_i + b_j \le k$ ). $k$ is an integer given as input.

Find the maximum possible sum of happiness values of the girls who are in dating relationships.

Input

The first line contains two integers $n$ and $k$ .

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ , the personality type and happiness value of the $i$ -th girl.

Output

Print one integer, the maximum possible sum of happiness values of the girls in dating relationships.

Constraints

$1 \le n \le 250\,000$
$1 \le k \le 10^9$
$1 \le a_i \le n$
$0 \le b_i \le k$

Examples4

Example 1
Input
```
4 5
1 2
1 3
2 1
2 4
```
Expected output
```
4
```
Example 2
Input
```
5 10
3 8
4 2
1 5
1 3
1 2
```
Expected output
```
17
```

Example 3

Input

Expected output

Example 4

Input

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

Expected output

4704511147