파티

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

요약

성격 유형이 서로 다른 소녀들끼리 짝을 지어 각 쌍의 행복도 합이 k 이하가 되도록 하고, 짝이 된 소녀들의 행복도 총합의 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 정렬, 투 포인터, 그리디
정답자: 아직 제출이 없습니다

문제

$n$ 명의 벚꽃소녀들이 파티를 열었다. 이 파티에서 벚꽃소녀들은 애인을 사귈 것이다. 애인 관계는 두 벚꽃소녀 사이에서 형성되며, 한 벚꽃소녀는 최대 하나의 애인 관계에만 속할 수 있다.

벚꽃소녀는 성격 종류 $a_i$ 와 행복도 $b_i$ 를 가진다. 두 벚꽃소녀 $i$ , $j$ 가 애인 관계를 형성하려면 두 벚꽃소녀의 성격 종류가 달라야 하고( $a_i \neq a_j$ ), 둘의 행복도 합이 $k$ 이하여야 한다( $b_i + b_j \le k$ ). $k$ 는 입력으로 주어지는 정수이다.

애인 관계에 속한 벚꽃소녀들의 행복도 합으로 가능한 최댓값은 얼마인가?

입력

첫 번째 줄에 두 정수 $n$ , $k$ 가 주어진다.

이후 $n$ 개의 줄에 걸쳐 각 벚꽃소녀의 정보가 주어진다. $i$ 번째 줄에는 두 정수 $a_i$ , $b_i$ 가 주어진다.

출력

애인 관계에 속한 벚꽃소녀들의 행복도 합으로 가능한 최댓값을 정수 하나로 출력한다.

제한

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

예제4

예제 1
입력
```
4 5
1 2
1 3
2 1
2 4
```
예상 출력
```
4
```
예제 2
입력
```
5 10
3 8
4 2
1 5
1 3
1 2
```
예상 출력
```
17
```

예제 3

입력

예상 출력

예제 4

입력

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

예상 출력

4704511147