#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
/* ok, bitset!!!
wait, is it possible that their's only one contestent that wants one kind of graph?
ok, let's just eliminate these cases, because sum_deg = 8n and we have4n points to consider if we make a graph from people i to left l_i and right r_i.
if we consider all the people and make a graph
if someone's deg = 1 then we know that we should take it and its neighbor, and wow, that's a matching problem!
first: find out if it has a perfect matching
iterate all the nodes deg = 1
we know people's deg = 2 so that L and R can do this
SAMITorz
second: bitsetorz
rings, choose the odd edges or the even edges, and do knapsack to find out if we can make the difference less then k
i want to make it like "b |= b<<k" or else
maybe the right side should have strength in [a,b];
we can find out how much we add to the right side
given an array A, an int x, for all elements C, you can add C to x or subtract C to x, find out if you can make abs(x) less then or equal to k
isn't it knapsack?
30000*30000*2*20/64 = 9e8 :EEEEE:
CF 1e9/s la
or greedy
greedy?
fine, since it's the only method i can figure out
let's gooooooooooo :TLEthinking:
*/
bitset<1200007> bt;
vector<vector<pair<int,int> > > g;
int main(){
AquA;
bt[0]=1;
int n,k;
cin >> n >> k;
g.resize(4*n);
vector<int> deg(4*n),vis(4*n);
int sum=0;
for(int i=0;i<2*n;i++){
int a,b,s;
cin >> a >> b >> s;
a--;
b--;
sum+=s;
g[a+2*n].push_back({i,s});
g[i].push_back({a+2*n,s});
g[b+3*n].push_back({i,s});
g[i].push_back({b+3*n,s});
deg[i]=2;
deg[a+2*n]++;
deg[b+3*n]++;
}
queue<int> q;
for(int i=2*n;i<4*n;i++){
if(deg[i]==1){
q.push(i);
}
if(deg[i]==0){
cout << "NO\n";
return 0;
}
}
while(q.size()){
auto h=q.front();
q.pop();
int flag=0;
for(auto y:g[h]){
if(!vis[y.fs]){
flag=1;
vis[y.fs]=1;
if(h>=3*n){
bt<<=y.sc;
}
for(auto z:g[y.fs]){
deg[z.fs]--;
if(deg[z.fs]==1){
q.push(z.fs);
}
}
}
}
if(!flag){
cout << "NO\n";
return 0;
}
}
for(int i=0;i<2*n;i++){
if(!vis[i]){
//dfs time :happy_mention:
int a=0,b=0;
for(int x=i,cnt=0,e=-1;cnt==0 || x!=i;cnt=1){
vis[x]=1;
for(auto f:g[x]){
if(f.fs==e){
continue;
}
if(f.fs>=3*n){
a+=f.sc;
}
for(auto y:g[f.fs]){
if(vis[y.fs] && (y.fs!=i || cnt==0)){
}
else{
if(f.fs>=3*n){
b+=y.sc;
}
x=y.fs;
e=f.fs;
break;
}
}
break;
}
}
//cout << a << " " << b << '\n';
bt=(bt<<a)|(bt<<b);
}
}
for(int i=0;i<=sum;i++){
if(bt[i]){
if(abs(i-(sum-i))<=k){
cout << "YES\n";
return 0;
}
}
}
cout << "NO\n";
return 0;
}
