#include #include #include #include using namespace std; using ll=long long; #include using mint=atcoder::modint998244353; ostream& operator<<(ostream& os,mint& x){ os<>(istream& is,mint& x){ int t; is>>t; x=t; return is; } template ostream& operator<<(ostream& os,const pair& p); template istream& operator>>(istream& is,pair& p); template ostream& operator<<(ostream& os,const array& arr); template istream& operator>>(istream& is,array& arr); template ostream& operator<<(ostream& os,const vector& vec); template istream& operator>>(istream& is,vector& vec); template ostream& operator<<(ostream& os,pair& p){ os< istream& operator>>(istream& is,pair& p){ is>>p.first>>p.second; return is; } template ostream& operator<<(ostream& os,array& arr){ for(int i=0;i istream& operator>>(istream& is,array& arr){ for(int i=0;i>arr[i]; return is; } template ostream& operator<<(ostream& os,vector& vec){ for(int i=0;i istream& operator>>(istream& is,vector& vec){ for(int i=0;i>vec[i]; return is; } template vector make_unique(vector vec){ ranges::sort(vec); vec.erase(unique(vec.begin(),vec.end()),vec.end()); return vec; } template vector make_rank(vector vec){ int n=vec.size(); vector res(n); iota(res.begin(),res.end(),0); ranges::sort(vec,{},[&](int i)->T{ return vec[i]; }); return res; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,d; cin>>n>>d; vector> dp(1<({(ll)1e5,(ll)1e5,(ll)1e5})); dp[0]={0ll,0ll,0ll}; vector> abc(n); cin>>abc; for(int i=0;i<(1<>j&1)continue; auto res=dp[i]; res[0]+=abc[j][0]; res[1]=max(res[0],res[1])+abc[j][1]; res[2]=max(res[1],res[2])+abc[j][2]; dp[i+(1<