Problem Description

Tug of War is a very popular sport in Byteland. The rules are simple: two teams pull the rope in opposite directions. The annual Byteland Tug of War competition is about to take place, and many contestants have signed up. As the commissioner of fair play, your job is to divide the contestants into two teams to ensure the competition lasts as long as possible.

Since there are $2n$ contestants, each team will have $n$ members. The rope has $n$ points on each side. The elite of Byteland's Tug of War are very particular, and each contestant has a preferred position on either side of the rope. Additionally, you know the strength value of each contestant.

The organizers are asking you the following question: given an integer $k$, is it possible to form two teams, each with $n$ contestants, and have them stand in their preferred positions (no more than one contestant can stand in the same position), with the difference in total strength between the two teams not exceeding $k$?

Input Format

The first line of input contains two positive integers $n$ and $k$, representing the number of positions on each side of the rope and the maximum allowable strength difference between the two teams, respectively. The contestants are numbered from $1$ to $2n$.

The next $2n$ lines describe each contestant. The $i$-th line contains three positive integers $l_i$, $r_i$, and $s_i$, representing that contestant $i$ has a strength of $s_i$ and wants to stand at position $l_i$ on the left side or position $r_i$ on the right side.

Output Format

Your program should output a single word YES or NO on the first line, indicating whether it is possible to form two teams that meet the above conditions.

Sample Input and Output

Sample Input #1

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

Sample Output #1

YES

Sample Input #2

2 5
1 1 1
1 2 4
2 2 1
2 1 4

Sample Output #2

NO

Notes/Hints

Sample Explanation 1

In the first example, we can arrange contestants $1, 3, 6, 7$ on the left side (the team's strength is $1+8+2+1=12$) and contestants $2, 4, 5, 8$ on the right side (the team's strength is $2+2+5+2=11$). The strength difference is $1$.

Sample Explanation 2

In the second example, the two contestants with strength $4$ must be on the same team, so the minimum strength difference between the two teams is $6$.

Subtasks

The following subtasks are for reference and are not related to the evaluation.

This problem is evaluated using subtasks, and you must correctly solve all test cases within a subtask to earn the points for that subtask.

For all subtasks, $k \le 20n$, $1 \le l_i, r_i \le n$, and $1 \le s_i \le 20$.

The conditions for each subtask are as follows:

Note: In reality, the outcome of a tug of war depends on the weight of the participants rather than their strength. The strength values in the problem should be proportional to the contestants' weights.

Acknowledgements

This problem was translated from LibreOJ, and the translator was HeRaNO. We thank the original translator for their contribution.

见题面 Input 部分

见题面 Output 部分