Tug of War

Tug of war is a very popular sport in Byteland. The rules are simple: two teams pull one rope in opposite directions. The annual Byteland charity tug of war is about to start, and a lot of contestants have signed up. As the fair play commissioner, your job is to split the contestants into two teams so that the game goes on for a long time.

A total of $2n$ contestants signed up, so each team has $n$ contestants. The rope has $n$ spots on the left side and $n$ spots on the right side. The tug of war elite of Byteland are a picky bunch: each contestant has exactly one spot on the left side and one spot on the right side that he or she wants to use. You also know the strength of every contestant.

The organizer fixes an integer $k$ and asks you the following. Is it possible to create two teams such that each team has $n$ contestants, every contestant uses one of the two spots he or she wants (no two contestants share a spot), and the sums of strengths of the two teams differ by at most $k$?

The first line contains a positive integer $n$, the number of spots on each side of the rope, and an integer $k$, the largest allowed difference of the teams' strengths ($1 \le n \le 1000$, $0 \le k \le 20n$). The contestants are numbered from 1 to $2n$.

Each of the following $2n$ lines describes one contestant. The $i$-th of these lines contains three positive integers $l_i$, $r_i$ and $s_i$ ($1 \le l_i, r_i \le n$, $1 \le s_i \le 20$). Contestant $i$ has strength $s_i$ and may use only spot $l_i$ on the left side of the rope or spot $r_i$ on the right side.

Print YES on the first and only line if two teams satisfying all of the requirements above can be created, and NO otherwise.

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

In the second example both contestants of strength 4 end up on the same team no matter what, so the smallest possible difference of the team strengths is 6.