Alliance Formation Challenge

In this problem, you are given a set of villages, each with a target contribution and available resources. The goal is to determine if it is possible to form alliances by pairing the villages so that for each pair, the combined available resources are at least the combined target contributions, and the difference in available resources does not exceed a given limit. More formally, for a pair of villages with targets (A_i) and (A_j) and resources (B_i) and (B_j), the alliance is valid if:

[ |B_i - B_j| \le D \quad \text{and} \quad B_i + B_j \ge A_i + A_j ]

You are given multiple test cases. For each test case, if the number of villages is odd then a complete pairing is impossible and the answer should be "NO". Otherwise, determine if a valid pairing exists that meets the conditions for every pair, and output "YES" or "NO" accordingly.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer (T) (the number of test cases).
• For each test case:
  • The first line contains two integers (N) and (D), where (N) is the number of villages and (D) is the maximum allowed difference in available resources for forming an alliance.
  • The next (N) lines each contain two integers (A) and (B), where (A) is the target contribution and (B) is the available resource of the village.

Note: (N) must be even for a complete pairing; if it is odd, the answer is automatically "NO".

outputFormat

For each test case, print a single line to standard output (stdout) containing "YES" if it is possible to form alliances that satisfy the conditions, or "NO" if not.## sample

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

YES
NO
NO
YES
NO