有n个垃圾，第i个垃圾的坐标为(xi,yi)，重量为wi。
有一个机器人，要按照编号从小到大的顺序捡起所有垃圾并扔进垃圾桶（垃圾桶在原点(0,0)）。
机器人可以捡起几个垃圾以后一起扔掉，但任何时候其手中的垃圾总重量不能超过最大载重C。两点间的行走距离为曼哈顿距离（即横坐标之差的绝对值加上纵坐标之差的绝对值）。
求出机器人行走的最短总路程（一开始，机器人在(0,0)处）
f[ i ] =max( f[ j ] + D0(i)-D0(j+1) + sumD(i) -sumD(j+1) ) sumw[i]-sumw[j+1] <=C
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e5+2;
int C,n,s[N],f[N],dis[N],x[N],y[N],sw[N];
int F(int i){
return f[i]-s[i+1]+dis[i+1];
}
int hh,tt,q[N];
void solve(){
cin>>C>>n;
int i,z;
for(i=1;i<=n;i++){
cin>>x[i]>>y[i]>>z;
dis[i]=abs(x[i])+abs(y[i]);
s[i]=s[i-1]+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
sw[i]=sw[i-1]+z;
}
hh=1,tt=0; q[++tt]=0;
for(i=1;i<=n;i++){
while(hh<=tt&&sw[i]-sw[q[hh]]>C) hh++;
f[i]=F(q[hh])+s[i]+dis[i];
while(hh<=tt&&F(i)<=F(q[tt])) tt--;
q[++tt]=i ;
}
cout<<f[n]<<endl;
}
signed main(){
int cas;
cin>>cas;
while(cas--){
solve();
if(cas) cout<<endl;
}
}