Tug of war

Input

The first line contains two integers $n$ and $k$ (1 \leq n \leq 30\,000, 1 \leq k \leq 20n) — the number of participants per team and the maximum allowable difference in the sum of the teams' strengths.

Each of the following $2n$ lines contains three integers l_i, r_i, and s_i (1 \leq l_i, r_i \leq n, 1 \leq s_i \leq 20). Here, l_i and r_i are the preferred positions on the left and right teams for the $i$-th participant, and s_i is their strength.

Output

Print «YES» on a single line if it is possible to form the teams according to the conditions. Otherwise, print «NO».

Examples

Note

In the first example, you can assign players $1,3,6$, and $7$ to the left team (team strength equals 1 + 8 + 2 + 1 = 12), and participants $2,4,5$, and $8$ to the right team (team strength equals 2 + 2 + 5 + 2 = 11). The difference in strengths is $1$.

In the second example, both players with strengths $4$ must be on the same team, resulting in a minimum strength difference of $6$.

Scoring

1. ($18$ points): n \leq 10;

2. ($30$ points): n \leq 2\,000;

3. ($23$ points): n \leq 30\,000, s_i = 1;

4. ($29$ points): n \leq 30\,000.