#define CUTOFF 5000

inline int section(const int& i,const int& sn){
    return i/sn;
}

long simulate(int n,vector<vector<int>>& queries){
    long* sum=new long[n+1];
    long res;
    for(int i=0;i<n+1;i++) sum[i]=0;
    
    int a,b,k;
    for(int i=0;i<queries.size();i++){
        a=queries[i][0];
        b=queries[i][1];
        k=queries[i][2];
        for(int i=a;i<=b;i++) sum[i]+=k;
    }
    res=*std::max_element(sum,sum+n+1);
    delete[] sum;
    return res;
}

long arrayManipulation(int n, vector<vector<int>> queries) {
//sqrt(n+1) = #sections
if(n<CUTOFF) return simulate(n,queries);
int sn=(int)std::sqrt((double)n+1);
long* sum=new long[n+1];
long* sections=new long[sn]; // [0 -- sqrt(n)) section 0, etc....
for(int i=0;i<n+1;i++) sum[i]=0;
for(int i=0;i<sn;i++) sections[i]=0;
long res;
int a,b,k;

for(int i=0;i<queries.size();i++){
    a=queries[i][0];
    b=queries[i][1];
    k=queries[i][2];
    if(b-a>2*sn){
        for(int j=a;j<sn*(section(a,sn)+1);j++) sum[j]+=k;
        for(int j=(section(a,sn)+1);(j+1)*sn<=b;j++) sections[j]+=k;
        for(int j=sn*section(b,sn);j<=b;j++) sum[j]+=k;
    }
}

for(int i=0;i<n+1;i++) sum[i]+=sections[section(i,sn)];
res=*std::max_element(sum,sum+n+1);
delete[] sum;
delete[] sections;
return res;
}