Tug of war

Tug of war is a popular sport with straightforward rules: two teams pull a rope in opposite directions. An annual tug of war competition is organized, and many participants have already signed up. Lady, the main organizer, needs to divide the participants into two teams.

There are $2n$ participants registered, so each team must consist of $n$ participants. The rope has $n$ spots on the left side and $n$ spots on the right, indicating where participants will stand.

Each participant has chosen exactly one spot on the left and one spot on the right where they prefer to stand. Additionally, Lady knows the strength of each participant. She is having trouble distributing the participants into two teams and needs your help. Your task is to determine if it's possible to divide the participants into two teams such that each participant stands on one of their chosen spots, no two participants share a spot, and the difference in the total strengths of the two teams does not exceed $k$.

Input

The first line contains two integers $n$ and $k$ ($1\le n\le 30,000$, $1\le k\le 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\le l_i,r_i\le n,1\le s_i\le 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\le 10$;

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

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

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