Problem Description

Tug of War is a very popular sport in Byteland. The rules are very simple: two teams pull a rope in opposite directions. The annual Byteland Tug of War tournament is about to be held, and many players have signed up. As the fair play officer, your job is to divide the players into two teams so that the match can last for a long time.

Since there are $2n$ players in total, each team has $n$ members. On the rope, there are $n$ positions on the left side and $n$ positions on the right side. Byteland’s tug of war elites are very picky: each player has one position they want to stand at on the left side and one position they want to stand at on the right side. Also, you know the strength value of each player.

The organizers now ask you the following question: given an integer $k$, is it possible to form two teams, each with $n$ players, such that they stand in the positions they want (of course, no two or more players can stand in the same position), and the difference between the total strengths of the two teams does not exceed $k$?

Input Format

The first line contains two positive integers $n,k$, representing the number of positions on each side of the rope and the maximum allowed difference in total strength between the two teams. For simplicity, we number the players from $1$ to $2n$.

In the next $2n$ lines, each line describes one player. The $i$-th of these lines contains three positive integers $l_i,r_i,s_i$, meaning that player $i$ has strength $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 satisfy the conditions above.

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

YES

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

NO

Hint

Sample Explanation 1

In the first sample, we can arrange players $1,3,6,7$ to stand on the left side (this team has total strength $1+8+2+1=12$), and arrange players $2,4,5,8$ to stand on the right side (this team has total strength $2+2+5+2=11$). The difference in total strength is $1$.

Sample Explanation 2

In the second sample, the two players with strength $4$ must be on the same team, so the minimum possible difference between the total strengths of the two teams is $6$.

Subtasks

The following subtasks are not related to judging and are for reference only.

This problem uses subtask-based scoring. You can get the score for a subtask only if all test points in that subtask are correct.

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

The conditions for each subtask are as follows:

Note: in fact, tug of war does not depend on strength, but on the weight of both sides. In the original problem, the players’ strength values should be proportional to their weights.

Notes

This translation is adapted and carried over from LibreOJ. The translator is HeRaNO, and we would like to thank the original translator here.

Translated by ChatGPT 5