Problem:
 Score : 100 points    Problem Statement Consider a string of length N consisting of 0 and 1 .
The score for the string is calculated as follows:   For each i ( 1 \leq i \leq M ), a_i is added to the score if the string contains 1 at least once between the l_i -th and r_i -th characters (inclusive).   Find the maximum possible score of a string.      Constraints  All values in input are integers.  1 \leq N \leq 2 × 10^5  1 \leq M \leq 2 × 10^5  1 \leq l_i \leq r_i \leq N  |a_i| \leq 10^9         Input Input is given from Standard Input in the following format:  N  M  l_1  r_1  a_1  l_2  r_2  a_2  :  l_M  r_M  a_M       Output Print the maximum possible score of a string.        Sample Input 1 5 3
1 3 10
2 4 -10
3 5 10      Sample Output 1 20  The score for 10001 is a_1 + a_3 = 10 + 10 = 20 .       Sample Input 2 3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30      Sample Output 2 90  The score for 100 is a_1 + a_2 = 100 + (-10) = 90 .       Sample Input 3 1 1
1 1 -10      Sample Output 3 0  The score for 0 is 0 .       Sample Input 4 1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000      Sample Output 4 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 5 6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7      Sample Output 5 10  For example, the score for 101000 is a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10 .

Solution (Python):
from operator import add
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class LazySegmetTree:
    def __init__(self, size, op_data, u_data, op_lazy, u_lazy, op_merge):
        """
        size: 元の配列の長さ
        op_data, u_data: クエリ関数、単位元
        op_lazy, u_lazy: 遅延作用の関数、単位元
        op_merge: dataとlazyとの演算
        """
        self.N = size
        self.op_data = op_data
        self.op_lazy = op_lazy
        self.op_merge = op_merge
        self.u_data = u_data
        self.u_lazy = u_lazy
        
        self.data = [0] * (2 * self.N)
        self.lazy = [u_lazy] * (2 * self.N)

    def initialize(self, arr):
        op = self.op_data
        for i, a in enumerate(arr, self.N):
            self.data[i] = a
        for i in reversed(range(1, self.N)):
            self.data[i] = op(self.data[i << 1], self.data[i << 1 | 1])

    def _propagate_top_down(self, L):
        op = self.op_lazy
        merge = self.op_merge
        unit = self.u_lazy
        for i in reversed(range(1, L.bit_length())):
            i = L >> i
            v = self.lazy[i]
            if v == unit:
                continue
            self.data[i] = merge(self.data[i], v)
            self.lazy[i << 1] = op(self.lazy[i << 1], v)
            self.lazy[i << 1 | 1] = op(self.lazy[i << 1 | 1], v)
            self.lazy[i] = unit

    def _propagate_bottom_up(self, i):
        merge = self.op_merge
        op = self.op_data
        while i > 1:
            i >>= 1
            self.data[i] = op(merge(self.data[i << 1], self.lazy[i << 1]),
                              merge(self.data[i << 1 | 1], self.lazy[i << 1 | 1]))

    def fold(self, L, R):
        res = self.u_data
        op = self.op_data
        merge = self.op_merge
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                res = op(res, merge(self.data[L], self.lazy[L]))
                L += 1
            if R & 1:
                R -= 1
                res = op(res, merge(self.data[R], self.lazy[R]))
            L >>= 1
            R >>= 1
        return res

    def update(self, i, val):  
        i += self.N
        i0 = i // (i & -i)
        self._propagate_top_down(i0)
        self.data[i] = self.op_merge(self.data[i], self.lazy[i])
        self.data[i] = self.op_data(val, self.data[i])
        self.lazy[i] = self.u_lazy
        self._propagate_bottom_up(i0)

    def range_update(self, L, R, val):
        op = self.op_lazy
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = op(val, self.lazy[L])
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = op(val, self.lazy[R])
            L >>= 1
            R >>= 1
        self._propagate_bottom_up(L0)
        self._propagate_bottom_up(R0)


def main():
    N, M = map(int, input().split())
    LRA = list(tuple(map(int, input().split())) for _ in range(M))
    LRA.sort(key=lambda x: x[1])

    op_data = max
    unit_data = -10 ** 18
    op_lazy = add
    unit_lazy = 0
    op_merge = add
    seg = LazySegmetTree(N + 1, op_data, unit_data,
                         op_lazy, unit_lazy, op_merge)

    p = 0
    for i in range(N):
        val = seg.fold(0, i + 1)
        seg.update(i + 1, val)
        while p < M and LRA[p][1] <= i + 1:
            l, r, a = LRA[p]
            p += 1
            seg.range_update(l, r + 1, a)

    print(seg.fold(0, N + 1))


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int,input().split())
interval=[[] for i in range(N)]
for i in range(M):
    l, r, a = map(int,input().split())
    interval[r-1].append((l-1, a))


INF = 10**30-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

dp=[0]*N 

for i in range(N):
    for j in range(len(interval[i])):
        l, a = interval[i][j]
        update(l, i+1, a)
    dp[i] = max(query(0, i+1), 0)
    update(i+1, i+2, dp[i]) 

print(dp[-1])

Solution (Python):
N, M = map(int,input().split())
interval=[[] for i in range(N)]
for i in range(M):
    l, r, a = map(int,input().split())
    interval[l-1].append((r-1, a))


INF = 10**30-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

dp=[0]*N

for i in range(N-1, -1, -1):
    for j in range(len(interval[i])):
        r, a = interval[i][j]
        update(i, r+1, a)
    dp[i] = max(query(0, N), 0)
    if i>0: 
        update(i-1, i, dp[i])

print(dp[0])

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    INF = float('inf')
    idEle = -INF
    def _binOpe(x, y):
        return x if x >= y else y
    def makeSegTreeLazy(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        lazy = [0] * (2*numPow2)
        return data, lazy, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iST, A):
        vIfSet = _getVIfSet(iST, A)
        data[iST] += vIfSet
        lazy[iST] += A
    def _getVIfSet(iST, A):
        return A
    def _getIndices(iSt, iEn):
        iSTs = []
        L = iSt + numPow2
        R = iEn + numPow2
        L0 = L // (L & -L)
        R0 = R // (R & -R)
        while L < R:
            if L < L0:
                iSTs.append(L)
            if R < R0:
                iSTs.append(R)
            L >>= 1
            R >>= 1
        while L:
            iSTs.append(L)
            L >>= 1
        return iSTs
    def _propagate(iST):
        v = lazy[iST]
        if v:
            _update1(2*iST, v)
            _update1(2*iST+1, v)
            lazy[iST] = 0
    def update(iSt, iEn, A):
        iSTs = _getIndices(iSt, iEn)
        for iST in reversed(iSTs):
            _propagate(iST)
        L = iSt + numPow2
        R = iEn + numPow2
        while L < R:
            if L & 1:
                _update1(L, A)
                L += 1
            if R & 1:
                R -= 1
                _update1(R, A)
            L >>= 1
            R >>= 1
        for iST in iSTs:
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        iSTs = _getIndices(iSt, iEn)
        for iST in reversed(iSTs):
            _propagate(iST)
        ans = idEle
        L = iSt + numPow2
        R = iEn + numPow2
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, M = map(int, input().split())
    LRs = [[] for _ in range(N+1)]
    for _ in range(M):
        L, R, A = map(int, input().split())
        LRs[R].append((L, A))

    data, lazy, numPow2 = makeSegTreeLazy(N+1)
    setInit([0]*(N+1))

    for R in range(1, N+1):
        v = getValue(0, R)
        v0 = getValue(R, R+1)
        update(R, R+1, v-v0)
        for L, A in LRs[R]:
            update(L, R+1, A)

    ans = getValue(0, N+1)
    print(ans)


solve()

Solution (Python):
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
interval=[[] for i in range(0,N)]
for i in range(0,M):
    l,r,a=map(int,input().split())
    interval[l-1].append((r-1,a))


INF = 10**30-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

Max=[0 for i in range(0,N)]
for i in range(N-1,-1,-1):
    for j in range(0,len(interval[i])):
        r,a=interval[i][j]
        update(i,r+1,-a)
    Max[i]=max(-query(0,N),0)
    if i>0:
        update(i-1,i,-Max[i])

print(Max[0])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        
        
        
        
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        for _ in range(self._logn):
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [[] for _ in range(n)]
    for _ in range(m):
        l, r, a = map(int, input().split())
        queries[l - 1].append((r, a))

    
    tree = LazySegmentTree([0] * n, max, 0, add, 0, add)

    
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) 
        for r, a in queries[i]:
            tree.range_act(i, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        A : array of monoid (M, dot, unit)
        (S, compose, identitiy) : sub monoid of End(M)
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] <- f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [[] for _ in range(n)]
    for _ in range(m):
        l, r, a = map(int, input().split())
        queries[l - 1].append((r, a))

    
    tree = LazySegmentTree([0] * n, max, 0, add, 0, add)

    
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) 
        for r, a in queries[i]:
            tree.range_act(i, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] = f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, readline().split())
    queries = [[] for _ in range(n)]
    A = map(int, read().split())
    for l, r, a in zip(A, A, A):
        queries[l - 1].append((r, a))

    
    tree = LazySegmentTree([0] * n, max, 0, add, 0, add)

    
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) 
        for r, a in queries[i]:
            tree.range_act(i, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] = f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [[] for _ in range(n)]
    for _ in range(m):
        l, r, a = map(int, input().split())
        queries[l - 1].append((r, a))

    
    tree = LazySegmentTree([0] * n, max, 0, add, 0, add)

    
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) 
        for r, a in queries[i]:
            tree.range_act(i, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        self._propagate(l)
        self._propagate(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

def resolve():
    n,m=map(int,input().split())
    R=[[] for _ in range(n)]
    for _ in range(m):
        l,r,a=map(int,input().split())
        l-=1; r-=1
        R[r].append((l,a))
    from operator import add
    dp=LazySegmentTree([0]*n,max,0,add,0,add)
    for r in range(n):
        dp.range_act(r,r+1,dp.sum(0,r))
        for l,a in R[r]:
            dp.range_act(l,r+1,a)
    print(dp.sum(0,n))
resolve()