Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

struct data{
	int t;
	ll p,f;
	data(){}
	data(int tt,ll pp,ll ff){
		t=tt;
		p=pp;
		f=ff;
	}

	bool operator<(const data &d)const{
		if(f==d.f)return p<d.p;
		return f<d.f;
	}
};

struct CHTrick{
	deque<P> lines;
	bool isMonoticX=true;
	CHTrick(bool flag=true){
		isMonoticX=flag;
	}

	bool check(P l1,P l2,P l3){
		return (l3.second-l2.second)*(l2.first-l1.first)>=(l2.second-l1.second)*(l3.first-l2.first);
	}

	void add(ll a,ll b){
		P line(a,b);
		while(lines.size()>=2 && check(*(lines.end()-2),lines.back(),line)){
			lines.pop_back();
		}
		lines.push_back(line);
	}

	ll f(int i,ll x){
		return lines[i].first*x+lines[i].second;
	}
	ll f(P line,ll x){
		return line.first*x+line.second;
	}

	bool comp(ll lv,ll rv){
		return lv<=rv;
	}

	ll get(ll x){
		if(isMonoticX){
			while(lines.size()>=2 && comp(f(0,x),f(1,x))){
				lines.pop_front();
			}
			return f(0,x);
		}else{
			int low=-1,high=lines.size()-1;
			while(high-low>1){
				int mid=(high+low)/2;
				if(comp(f(mid,x),f(mid+1,x)))low=mid;
				else high=mid;
			}
			return f(high,x);
		}
	}
};

int n,T;
data d[4005];

CHTrick dp[4005];

int main(void){
	scanf("%d%d",&n,&T);
	for(int i=0;i<n;i++){
		scanf("%d%lld%lld",&d[i].t,&d[i].p,&d[i].f);
	}
	sort(d,d+n);
	dp[0].add(0,0);
	ll ans=0;
	for(int i=0;i<n;i++){
		for(int j=T-d[i].t;j>=0;j--){
			if(dp[j].lines.size()==0)continue;
			ll v=dp[j].get(d[i].f)+d[i].p-d[i].f*d[i].f;
			if(j==0){
				v+=d[i].f*d[i].f;
			}
			ans=max(v,ans);
			dp[j+d[i].t].add(2LL*d[i].f,v-d[i].f*d[i].f);
		}
	}
	printf("%lld\n",ans);
	return 0;
}