rt，方程 $dp_{i,j}=\min\{dp_{i-1,k}+(x_i-x_{i-1})\times k^2-c_i\times k\}+c_i\times j (j-f_i\leq k\leq j)$

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define LL long long

const int N=5e2+5;
const int M=1e4+5;

int m,hm,n,hd,tl;
LL dis[N],f[N],c[N],dp[N][M];

struct node{
	int id;LL val;
}q[N];

struct edge{
	LL d,f,c;
}a[N]; 

bool cmp(edge a,edge b){
	return a.d<b.d;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>m>>hm>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].d>>a[i].f>>a[i].c;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		dis[i]=a[i].d;
		f[i]=a[i].f;
		c[i]=a[i].c;
	}
	for(int i=0;i<=f[1];i++){
		dp[1][i]=c[1]*i;
	}
	for(int i=2;i<=n;i++){
		hd=1,tl=0;
		for(int j=0;j<=m;j++){
			LL va=dp[i-1][j]+(dis[i]-dis[i-1])*j*j-c[i]*j;
			while(va<=q[tl].val&&hd<=tl) tl--;
			q[++tl]=(node){j,va};
			while(q[hd].id<j-f[i]&&hd<=tl) hd++;
			LL fr=q[hd].val;
			dp[i][j]=fr+c[i]*j;
		}
	}
	cout<<(LL)dp[n][m]+m*m*(hm-dis[n])<<"\n";
	return 0;
}