rt,分组后树形背包,写的有点shi山（qwq

dalao求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=407;
const int M=1e5+7;
int n,m,p,x[N],y[N],t[N],val[N],f[N][N],tot=0,fa[N];
vector<int>e[M<<1],s[N]; 
set<int>sz;
inline bool cmp(int xx,int yy){
	if(x[xx]!=x[yy])return x[xx]<x[yy];
	return y[xx]<y[yy];
}
inline int find(int x){
    if(x!=fa[x])return fa[x]=find(fa[x]);
    return x;
}
inline void solve(int u,int m){
    if(m<=0)return;   
    for(int v:e[u]){
        solve(v,m-t[v]);   
        for(int j=m;j>=t[v];j--)f[u][j]=max(f[u][j],f[u][j]+f[v][j-t[v]]+val[v]); 
    }
}
bool vis[N];
inline void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	for(auto v:e[u]){
		cout<<u<<"->"<<v<<"\n";
		dfs(v);
	}
	return;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>t[i]>>val[i];
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(x[i]*y[j]==x[j]*y[i]){
			    int fu=find(i),fv=find(j);
				if(fu!=fv)fa[fu]=fv;
			}
		}
	} 
//	for(int i=1;i<=n;i++)cout<<find(i)<<" ";
//	cout<<"\n";
	for(int i=1;i<=n;i++){
		int f=find(i);
		s[f].push_back(i);
		sz.insert(f);
	}
	for(auto x:sz)sort(s[x].begin(),s[x].end(),cmp);
	for(auto x:sz){
		int len=s[x].size();
		for(int i=1;i<len;i++){
			int u=s[x][i-1],v=s[x][i];
			e[u].push_back(v);
		}
	}
//	for(auto x:sz){
//		int len=s[x].size();
//		for(int i=0;i<len;i++)
//			cout<<s[x][i]<<" ";
//		cout<<"\n";
//	}
	for(auto x:sz)
		e[0].push_back(s[x][0]);
//	dfs(0);
	solve(0,m);
	cout<<f[0][m]<<"\n";
}