CF1648D Serious Business

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define int long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=5e5+10;
int n,q,a[4][N],Ans;
struct Que{int l,r,k;}g[N];
struct node{int l,r,v;}O;
I node operator+(Cn node& x,Cn node& y){return (node){max(x.l,y.l),max(x.r,y.r),max(max(x.v,y.v),x.l+y.r)};}
class SegmentTree{
    private:
        node T[N<<2];
        #define mid (l+r>>1)
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PT CI x=1,CI l=1,CI r=n
        #define PU(x) (T[x]=T[x<<1]+T[x<<11])
    public:
        I void B(PT){
            if(l==r) return void(T[x]=(node){a[1][l]-a[2][l-1],a[2][l]+a[3][n]-a[3][l-1],a[1][l]-a[2][l-1]+a[2][l]+a[3][n]-a[3][l-1]});
            B(LT),B(RT),PU(x);
        }
        I void U(CI p,CI v,PT){
            if(l==r) return T[x].l=max(T[x].l,v),T[x].v=T[x].l+T[x].r,void();
            p<=mid?U(p,v,LT):U(p,v,RT),PU(x);
        }
        I node Q(CI L,CI R,PT){
            if(L<=l&&r<=R) return T[x];
            if(R<=mid) return Q(L,R,LT);if(L>mid) return Q(L,R,RT);
            return Q(L,R,LT)+Q(L,R,RT);
        }
}T;
signed main(){
    RI i,j;for(read(n,q),i=1;i<=3;i++) for(j=1;j<=n;j++) read(a[i][j]),a[i][j]+=a[i][j-1];for(i=1;i<=q;i++) read(g[i].l,g[i].r,g[i].k);
    for(sort(g+1,g+q+1,[&](Cn Que& x,Cn Que& y){return x.r<y.r;}),T.B(),Ans=-2e18,i=1;i<=q;i++)
        O=T.Q(g[i].l,g[i].r),Ans=max(Ans,O.v-g[i].k),g[i].r<n&&(T.U(g[i].r+1,O.l-g[i].k),0);return writeln(Ans),0;
}