Swapping Pairs

5

1 votes
Dynamic Programming, 2D dynamic programming, Algorithms
Problem

You are given N pairs (A1,B1), (A2,B2), ..., (AN,BN). You are also given an integer M.

You can swap any pair, that is, for the ith pair, Ai becomes Bi and Bi becomes Ai. You have to apply this operation in such a way that, 

Ni=1Ai=M

Your task is to determine whether the conditions can be satisfied or not. If the condition can be satisfied, then print YES, otherwise print NO.

Input Format

  • The first line contains an integer T denoting the number of test cases. Description of each test case is as follows:
  • The first line of each test case contains two space-seperated integers N and M.
  • The next N lines contains two space-seperated integers Ai and Bi denoting the ith pair.

Output Format

For each test case, print YES, if it is possible to satisfy the given condition, otherwise print NO.

Constraints

1T100

1N1000

1M10000

1Ai, Bi1000

It is guaranteed that the sum of values of N over all test cases in the input does not exceed 1000.

Sample Input
3
2 5
4 10
5 1
2 3
2 1
4 3
4 19
3 7
1 4
6 9
3 6
Sample Output
YES
NO
YES
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

In the first test case, you can swap the 2nd pair. Thus, the sum will be 4+1=5.

In the second test case, we can show that there is no possible way to satisfy the condition.

In the third test case, there are multiple ways of satisfying the condition. One of the possible ways is to swap the 2nd and 4th pairs.

Editor Image

?