把 (b_i - |a_i - x|) 的 (b_i) 提出来然后单调队列就没了。
// clang-format off
// powered by c++11
// by Isaunoya
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define Rep(i,x,y) for(register int i=(x);i>=(y);--i)
using namespace std;
using db=double;
using ll=long long;
using uint=unsigned int;
using ull=unsigned long long;
using pii=pair<int,int>;
#define Tp template
#define fir first
#define sec second
Tp<class T>void cmax(T&x,const T&y) {
if(x<y)x=y;
}
Tp<class T>void cmin(T&x,const T&y) {
if(x>y)x=y;
}
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
#define pb emplace_back
Tp<class T>void sort(vector<T>&v) {
sort(all(v));
}
Tp<class T>void reverse(vector<T>&v) {
reverse(all(v));
}
Tp<class T>void unique(vector<T>&v) {
sort(all(v)),v.erase(unique(all(v)),v.end());
}
inline void reverse(string&s) {
reverse(s.begin(),s.end());
}
const int SZ=1<<23|233;
struct FILEIN {
char qwq[SZ],*S=qwq,*T=qwq,ch;
#ifdef __WIN64
#define GETC getchar
#else
inline char GETC() {
return(S==T)&&(T=(S=qwq)+fread(qwq,1,SZ,stdin),S==T)?EOF:*S++;
}
#endif
inline FILEIN&operator>>(char&c) {
while(isspace(c=GETC()));
return*this;
} inline FILEIN&operator>>(string&s) {
s.clear();
while(isspace(ch=GETC()));
if(!~ch)return*this;
s=ch;
while(!isspace(ch=GETC())&&~ch)s+=ch;
return*this;
}
inline FILEIN&operator>>(char*str) {
char*cur=str;
while(*cur)*cur++=0;
cur=str;
while(isspace(ch=GETC()));
if(!~ch)return*this;
*cur=ch;
while(!isspace(ch=GETC())&&~ch)*++cur=ch;
*++cur=0;
return*this;
}
Tp<class T>inline void read(T&x) {
bool f=0;
while((ch=GETC())<48&&~ch)f^=(ch==45);
x=~ch?(ch^48):0;
while((ch=GETC())>47)x=x*10+(ch^48);
x=f?-x:x;
}
inline FILEIN&operator>>(int&x) {
return read(x),*this;
} inline FILEIN&operator>>(ll&x) {
return read(x),*this;
} inline FILEIN&operator>>(uint&x) {
return read(x),*this;
} inline FILEIN&operator>>(ull&x) {
return read(x),*this;
}
inline FILEIN&operator>>(double&x) {
read(x);
bool f=x<0;
x=f?-x:x;
if(ch^'.')return*this;
double d=0.1;
while((ch=GETC())>47)x+=d*(ch^48),d*=.1;
return x=f?-x:x,*this;
}
} in;
struct FILEOUT {
const static int LIMIT=1<<22;
char quq[SZ],ST[233];
int sz,O,pw[233];
FILEOUT() {
set(7);
rep(i,pw[0]=1,9)pw[i]=pw[i-1]*10;
}~FILEOUT() {
flush();
}
inline void flush() {
fwrite(quq,1,O,stdout),fflush(stdout),O=0;
}
inline FILEOUT&operator<<(char c) {
return quq[O++]=c,*this;
} inline FILEOUT&operator<<(string str) {
if(O>LIMIT)flush();
for(char c:str)quq[O++]=c;
return*this;
}
inline FILEOUT&operator<<(char*str) {
if(O>LIMIT)flush();
char*cur=str;
while(*cur)quq[O++]=(*cur++);
return*this;
}
Tp<class T>void write(T x) {
if(O>LIMIT)flush();
if(x<0) {
quq[O++]=45;
x=-x;
}
do {
ST[++sz]=x%10^48;
x/=10;
} while(x);
while(sz)quq[O++]=ST[sz--];
}
inline FILEOUT&operator<<(int x) {
return write(x),*this;
} inline FILEOUT&operator<<(ll x) {
return write(x),*this;
} inline FILEOUT&operator<<(uint x) {
return write(x),*this;
} inline FILEOUT&operator<<(ull x) {
return write(x),*this;
}
int len,lft,rig;
void set(int l) {
len=l;
} inline FILEOUT&operator<<(double x) {
bool f=x<0;
x=f?-x:x,lft=x,rig=1.*(x-lft)*pw[len];
return write(f?-lft:lft),quq[O++]='.',write(rig),*this;
}
} out;
#define int long long
struct Math {
vector<int>fac,inv;
int mod;
void set(int n,int Mod) {
fac.resize(n+1),inv.resize(n+1),mod=Mod;
rep(i,fac[0]=1,n)fac[i]=fac[i-1]*i%mod;
inv[n]=qpow(fac[n],mod-2);
Rep(i,n-1,0)inv[i]=inv[i+1]*(i+1)%mod;
}
int qpow(int x,int y) {
int ans=1;
for(; y; y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;
return ans;
} int C(int n,int m) {
if(n<0||m<0||n<m)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int gcd(int x,int y) {
return!y?x:gcd(y,x%y);
} int lcm(int x,int y) {
return x*y/gcd(x,y);
}
} math;
// clang-format on
int n, m, d;
const int maxn = 2e5 + 52;
int t[2], f[2][maxn], q[maxn];
int ans = 1e18;
signed main() {
//code begin.
in >> n >> m >> d;
int p = 0, sum = 0;
rep(i , 1 , m) {
int a, b;
in >> a >> b >> t[p ^ 1];
sum += b;
int len = (t[p ^ 1] - t[p]) * d;
int head = 1, tail = 0;
rep(j , 1 , n) {
while(head <= tail && q[head] < j - len)
++ head;
while(head <= tail && f[p][q[tail]] > f[p][j])
-- tail;
q[++ tail] = j;
f[p ^ 1][j] = f[p][q[head]] + abs(a - j);
}
head = 1, tail = 0;
Rep(j , n , 1) {
while(head <= tail && q[head] > j + len)
++ head;
while(head <= tail && f[p][q[tail]] > f[p][j])
-- tail;
q[++ tail] = j;
cmin(f[p ^ 1][j], f[p][q[head]] + abs(a - j));
}
p ^= 1;
}
rep(i , 1 , n) cmin(ans, f[p][i]);
out << sum - ans << '
';
return 0;
//code end.
}