Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T1,typename T2> void chmin(T1 &a,T2 b){if(a>b)a=b;};
template<typename T1,typename T2> void chmax(T1 &a,T2 b){if(a<b)a=b;};

template <typename T>
struct ConvexHullTrick{
  using P = pair<T,T>;
  deque<P> L;
  Int isdec;

  ConvexHullTrick():isdec(-1){}

  inline T getY(const P &a, const T &x){
    return a.first * x + a.second;
  }

  inline bool check(const P &a, const P &b, const P &c){
    return (b.first - a.first) * (c.second - b.second)
      >= (b.second - a.second) * (c.first - b.first);
  }
  inline bool empty(){return L.empty();}

  void add(T a, T b){
    //cout<<isdec<<":"<<a<<" "<<b<<endl;
    a*=-1;b*=-1;
    P line(a, b);
    if(isdec == -1 && !L.empty()){
      if(a < L[0].first) isdec = 1;
      else if(a > L[0].first) isdec = 0;
    }

    if(isdec){
      if(!L.empty() && L.back().first == a){
	line.second = min(line.second, L.back().second);
	L.pop_back();
      }
      while(L.size() >=2 && check(*prev(L.end(), 2), L.back(), line)) L.pop_back();
      L.emplace_back(line);
    } else {
      if(!L.empty() && L.front().first == a){
	line.second = min(line.second, L.front().second);
	L.pop_front();
      }
      while(L.size() >= 2 && check(L[0], L[1], line)) L.pop_front();
      L.emplace_front(line);
    }
  }

  T get(T x){
    Int low = -1, high = L.size()-1;
    while(low+1 < high){
      Int mid = (low + high) >> 1;
      if(getY(L[mid], x) >= getY(L[mid+1], x)) low = mid;
      else high = mid;
    }
    return -getY(L[high], x);
  }

  T getMonotone(T x){
    while(L.size() >= 2 && getY(L[0], x) >= getY(L[1], x)) L.pop_front();
    return -getY(L[0], x);
  }    
};

const Int MAX = 4040;
Int dp[MAX][MAX];

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);


  Int n,x;
  cin>>n>>x;
  vector<Int> t(n),p(n),f(n);
  for(Int i=0;i<n;i++) cin>>t[i]>>p[i]>>f[i];

  const Int INF = 1e15;
  for(Int i=0;i<MAX;i++)
    for(Int j=0;j<MAX;j++)
      dp[i][j]=-INF;
  
  using T = tuple<Int, Int, Int>;
  vector<T> vt(n);
  for(Int i=0;i<n;i++) vt[i]=T(f[i],p[i],t[i]);
  sort(vt.begin(),vt.end());
  for(Int i=0;i<n;i++) tie(f[i],p[i],t[i])=vt[i];
  //for(Int i=0;i<n;i++) cout<<f[i]<<" "<<p[i]<<" "<<t[i]<<endl;
  
  Int ans=0;
  vector<ConvexHullTrick<Int> > vh(MAX);
  
  for(Int i=0;i<n;i++){
    for(Int j=x;j>t[i];j--){
      if(vh[j-t[i]].L.empty()) continue;
      chmax(dp[i][j],vh[j-t[i]].getMonotone(f[i])+p[i]-f[i]*f[i]);
      vh[j].add(2*f[i],dp[i][j]-f[i]*f[i]);      
      chmax(ans,dp[i][j]);
    }
    chmax(dp[i][t[i]],p[i]);
    vh[t[i]].add(2*f[i],dp[i][t[i]]-f[i]*f[i]);   
    chmax(ans,dp[i][t[i]]); 
  }
  cout<<ans<<endl;
  return 0;
}