합이 $K$ 이하

면접 대비

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

요약

N개의 순서쌍 (a_i, b_i)에서 a 값이 서로 다른 두 원소의 b 합 b_i + b_j 중 K 이하인 가장 큰 값을 찾는다.

난이도: 보통10점 중 5점
유형: 정렬, 투 포인터, 배열, 이분 탐색
정답자: 아직 제출이 없습니다

문제

$N$ 개의 순서쌍 $(a\_1, b\_1), (a\_2, b\_2), \cdots, (a\_N, b\_N)$ 이 있다. $a\_i \ne a\_j$ 인 모든 쌍 $(i, j)$ 에 대해 구한 $b\_i + b\_j$ 중 $K$ 이하인 가장 큰 수를 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 $N$ 과 $K$ 가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N+1$ 번째 줄까지 $N$ 개 줄에 걸쳐서 $i+1$ 번째 줄에 두 정수 $a\_i$ , $b\_i$ 가 공백으로 구분되어 주어진다. $(1 \le i \le N)$

출력

조건을 만족하는 수 중 가장 큰 수를 출력한다. 만약 그러한 수가 없으면 NO를 출력한다.

제한

$2 \le N \le 10^5$
$-10^9 \le a\_i, b\_i \le 10^9$ $(1 \le i \le N)$
$-2 \times 10^9 \le K \le 2 \times 10^9$
$a\_i \ne a\_j$ 인 $i, j$ 가 존재한다.

예제2

예제 1
입력
```
4 10
1 4
1 5
2 3
3 4
```
예상 출력
```
9
```
예제 2
입력
```
3 5
1 -1
-3 7
3 9
```
예상 출력
```
NO
```