페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8514
스페셜 저지
채점 보류

Doubles Horseback Wrestling 4s 1024MB

문제

The Nomadic Games Exploratory Committee (NGEC) is floating the idea of a doubles horseback wrestling tournament with pairs of riders astride single horses. They have advertised a pilot tournament, and n eager riders have signed up to compete! So now the NGEC needs to pair the riders in order to make the tournament both fair and exciting.

The Central Asian Audaryspak League (CAAL) maintains a list of all horseback wrestlers and their ratings. From their previous experience with ordinary horseback wrestling, the NGEC has decided that the pairs are best balanced if the ratings of their two riders add up to a particular integer, s.

For obscure licensing reasons, the CAAL refuses to release the exact rating of each rider. But the NGEC has some good estimates, knowing that any rider i’s true rating r_i lies in an interval [l_i, u_i]. So the NGEC would consider pairing two riders i and j if there are ratings r_i \in [l_i, u_i] and r_j \in [l_j , u_j] such that r_i + r_j = s.

The NGEC wants to form as many non-intersecting pairs of riders as possible. You need to help them.


입력

The first line contains two integers n and s (2 ≤ n ≤ 2 \cdot 10^5, 1 ≤ s ≤ 10^9), denoting the number of riders and the desired sum of ratings of riders in a pair. Riders are numbered 1 to n. This is followed by n lines, where the ith line contains two integers l_i and u_i (1 ≤ l_i ≤ u_i ≤ 10^9), denoting the rating range of the ith rider.


출력

Output k, the maximum number of riding pairs that can be formed, followed by k pairs of integers, denoting the numbers of the riders forming each pair. If there are multiple ways to pair off the riders, output any one.


예제 

6 10
6 7
1 4
2 2
3 8
5 7
9 9
2
6 2
3 4

출처

ICPC World Finals 2024 D

로그인해야 코드를 작성할 수 있어요.