I know how to solve it,but I just can't code it correctly...

I use splay to implement it,and the third test case of the sample's answer is wrong.

code:

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
il void cmin(ll &x,ll y){x=x<y?x:y;}
il int ab(int x){return x>0?x:-x;}
const int N=2e5+5,inf=1e9;
int T,n;ll f[N],g[N],sum;
struct node{
    int s[2],fa,v,siz;ll w;
    il node(){s[0]=s[1]=fa=v=siz=0,w=0;}
}t[N];ll tag[N];int tot,rt;
il void PRINT(){
    puts("----------------- TREE STRUCTURE");
    for(int i=0;i<=tot;++i) printf("%d %d %d %d\n",i,t[i].fa,t[i].s[0],t[i].s[1]);puts("");
}
il int get(int x){return t[t[x].fa].s[1]==x;}
il void INIT(int x){t[x].s[0]=t[x].s[1]=t[x].fa=t[x].v=t[x].siz=0,t[x].w=tag[x]=0;}
il int NEW(int fa,int v,ll w){int x=++tot;t[x].s[0]=t[x].s[1]=0,t[x].fa=fa,t[x].v=v,t[x].siz=1,t[x].w=w;return x;}
il void pushup(int x){t[x].siz=t[t[x].s[0]].siz+t[t[x].s[1]].siz+1;}
il void rot(int x){
    if(!x) return ;
    //printf("- 1 %d %d\n",x,t[0].siz);
    int y=t[x].fa,z=t[y].fa,c=get(x),u=t[x].s[!c];
    t[z].s[get(y)]=x,t[x].fa=z;
    t[y].s[c]=u,t[u].fa=y;
    t[x].s[!c]=y,t[y].fa=x;
    /*if(!y || !x){
        printf("--------------- *** %d %d %d\n",x,y,z);
        exit(0);
    }*/
    //printf("- 2 %d %d\n",x,t[0].siz);
    pushup(y),pushup(x);
}
il void maketag(int x,ll w){if(x) t[x].w+=w,tag[x]+=w;}
il void pushdown(int x){
    if(!x) return ;
    if(tag[x]) maketag(t[x].s[0],tag[x]),maketag(t[x].s[1],tag[x]),tag[x]=0;
}
il void build(int &x,int l,int r){
    if(l>r) return ;
    if(!x) x=++tot;
    if(l==r){t[x].v=(l?inf:-inf),t[x].siz=1;return ;}
    int mid=(l+r)>>1;t[x].v=mid,t[x].w=f[1],t[x].siz=1;
    if(l<=mid-1) build(t[x].s[0],l,mid-1),t[t[x].s[0]].fa=x;
    if(mid+1<=r) build(t[x].s[1],mid+1,r),t[t[x].s[1]].fa=x;
    pushup(x);
}
il void splay(int x,int to){
    int y,z;
    while(t[x].fa!=to){
        if(!x) break;
        y=t[x].fa,z=t[y].fa,pushdown(z),pushdown(y),pushdown(x);
        if(z!=to){
            if(get(x)==get(y)) rot(y);else rot(x);
        }rot(x);
    }if(!to) rt=x;
}
il int get_v(int k){
    int x=rt,y,z;++k;
    while(k){
        y=t[x].s[0];pushdown(x);
        if(k<=t[y].siz) x=y;
        else if(k>t[y].siz+1) k-=t[y].siz+1,x=t[x].s[1];
        else return x;
    }return 0;
}
il void insert(int p,ll w){
    /*if(t[0].siz){
        puts("befffff ********************************************");
        printf("%d %lld\n",p,w);
        PRINT();
        exit(0);
    }*/
    int x=get_v(p),y=get_v(p+1),z=-1;
    /*if(t[0].siz || !x || !y || !z){
        puts("bef ********************************************");
        printf("%d %d %d %d %lld\n",x,y,z,p,w);
        PRINT();
        exit(0);
    }*/
    splay(x,0),splay(y,x);
    /*if(t[0].siz || !x || !y || !z){
        puts("********************************************");
        printf("%d %d %d %d %lld\n",x,y,z,p,w);
        PRINT();
        exit(0);
    }*/
    z=NEW(y,p+1,w),t[y].s[0]=z;
    /*if(t[0].siz || !x || !y || !z){
        puts("********************************************");
        printf("%d %d %d %d %lld\n",x,y,z,p,w);
        PRINT();
        exit(0);
    }*/
    pushup(y),pushup(x);
}
il void update(int l,int r,ll w){
    int x=get_v(l-1),y=get_v(r+1),z;splay(x,0),splay(y,x),z=t[y].s[0];
    /*if(t[0].siz || !x || !y || !z){
        puts("********************************************");
        printf("%d %d %d %d %d %lld\n",x,y,z,l,r,w);
        PRINT();
        exit(0);
    }*/
    pushdown(x),pushdown(y);
    maketag(z,w);
    pushup(y),pushup(x);
}
il ll query(int p){
    int x=get_v(p-1),y=get_v(p+1),z;splay(x,0),splay(y,x),z=t[y].s[0];
    /*if(t[0].siz || !x || !y || !z){
        puts("********************************************");
        printf("%d %d %d %d\n",x,y,z,p);
        PRINT();
        exit(0);
    }*/
    pushdown(x),pushdown(y);
    return t[z].w;
}
int getnxt(int x,int cur,ll K,ll B){
    //if(t[0].siz) puts("***");
    if(!x) return 0;
    int y=t[x].s[0],z=t[x].s[1],p;ll u,v,w;
    if(ab(t[x].v)==inf) return y?getnxt(y,cur,K,B):getnxt(z,cur+t[y].siz+1,K,B);
    pushdown(x);
    u=t[x].w,v=K*(1ll*cur+t[y].siz)+B;
    if(u<=v){
        p=(z?getnxt(z,cur+t[y].siz+1,K,B):0);
        return p?p:cur+t[y].siz;
    }
    else return getnxt(y,cur,K,B);
}
struct P{
    ll a,b,k;
    il P(){a=b=k=0;}
}a[N];
il bool cmp(P x,P y){return x.k>y.k;}
il void init(){
    for(int i=0;i<=tot;++i) INIT(i);
    rt=tot=0;
}
int x,y,z;ll u,v,w;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);sum=0,init();
        for(int i=1;i<=n;++i) scanf("%lld%lld%lld",&a[i].k,&a[i].b,&a[i].a),sum+=a[i].a;
        sort(a+1,a+1+n,cmp);
        for(int i=0;i<=n+1;++i) f[i]=0;
        f[1]=a[1].k-(a[1].b-a[1].a);
        build(rt,0,2);//printf("%d\n",get_v(2)),PRINT();
        for(int i=1;i<=n;++i){
            x=0,w=a[i].b-a[i].a;
            //while(x<i-1 && f[x+1]<=a[i].k*(x+1ll)-w) ++x;
            //printf("*********** %d %d\n",i,t[0].siz);
            x=getnxt(rt,0,a[i].k,-w);
            //printf("------------*********** %d %d %d\n",i,x,t[0].siz);
            insert(x,a[i].k*(x+1ll)-w);
            //printf("-------------------------*********** %d %d\n",i,t[0].siz);
            if(x+2<=i) update(x+2,i,a[i].k);
           // printf("*********** %d %d\n",i,t[0].siz);
           // for(int j=i;j>x+1;--j) f[j]=f[j-1]+a[i].k;
            //f[x+1]=a[i].k*(x+1ll)-w;
        }
        w=0,v=0;for(int i=1;i<=n;++i) cmin(w,v+=query(i));
        printf("%lld\n",sum-w);
        init();
    }
    return 0;
}
/*
1
4
10000 1000000000 2006
10000 1000000000 9999
2 999991010 1010
1000000000 1000000000 999999999
*/