Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive.  Once all operations have been performed, return the maximum value in the array.  

Example 

$n=10$ 

$queries=[[1,5,3],[4,8,7],[6,9,1]$  

Queries are interpreted as follows:  

    a b k
    1 5 3
    4 8 7
    6 9 1

Add the values of $\boldsymbol{\mbox{k}}$ between the indices $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is $10$ after all operations are performed.  

Function Description  

Complete the function arrayManipulation in the editor below.  

arrayManipulation has the following parameters:

int n - the number of elements in the array  
int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.  

Returns  

int - the maximum value in the resultant array  

Input Format

The first line contains two space-separated integers $n$ and $m$, the size of the array and the number of operations. 

Each of the next $m$ lines contains three space-separated integers $\class{ML__boldsymbol}{\boldsymbol{a}}$, $\boldsymbol{b}$ and $\boldsymbol{\mbox{k}}$, the left index, right index and summand.  

Constraints

$3\leq n\leq10^7$  
$1\leq m\leq2*10^5$  
$1\leq a\leq b\leq n$  
$0\leq k\leq10^9$  

Sample Input
5 3
1 2 100
2 5 100
3 4 100

Sample Output
200

Explanation

After the first update the list is 100 100 0 0 0. 

After the second update list is 100 200 100 100 100. 

After the third update list is 100 200 200 200 100.  

The maximum value is $\textbf{200}$.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
(N, M) = [int(_) for _ in input().split(' ')]
Is = {}
for m in range(M):
	(a, b, k) = [int(_) for _ in input().strip().split(' ')]
	if k == 0:
		continue
	Is[a] = Is.get(a, 0) + k
	Is[b + 1] = Is.get(b + 1, 0) - k
(m, v) = (0, 0)
for i in sorted(Is):
	v += Is[i]
	if v > m:
		m = v
print(m)


import heapq
(N, M) = [int(v) for v in input().split()]
heap = []
for Mi in range(M):
	(a, b, k) = [int(v) for v in input().split()]
	heapq.heappush(heap, (a, +k))
	heapq.heappush(heap, (b + 1, -k))
mr = 0
cr = 0
while len(heap) > 0:
	item = heapq.heappop(heap)
	cr += item[1]
	mr = max(mr, cr)
print(mr)


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


from collections import defaultdict
(N, M) = map(int, input().split())
A = [0 for i in range(N + 2)]
for i in range(M):
	(a, b, k) = map(int, input().split())
	A[a] += k
	A[b + 1] -= k
for i in range(1, len(A)):
	A[i] += A[i - 1]
print(max(A))


(N, M) = (int(_) for _ in input().split())
A = [0] * (N + 1)
for _ in range(M):
	(a, b, k) = (int(_) for _ in input().split())
	A[a - 1] += k
	A[b] -= k
(m, v) = (0, 0)
for a in A:
	v += a
	if v > m:
		m = v
print(m)


(N, M) = [int(i) for i in input().split()]
li = [0] * N
for _ in range(M):
	(a, b, k) = [int(i) for i in input().split()]
	li[a - 1] += k
	try:
		li[b] -= k
	except:
		pass
t = li[0]
for i in range(1, N):
	li[i] += li[i - 1]
	if li[i] > t:
		t = li[i]
print(t)


n = input().split()
m = int(n[1])
n = int(n[0])
arr = [0] * n
for i in range(m):
	a = input().split()
	b = int(a[1])
	k = int(a[2])
	a = int(a[0])
	arr[a - 1] += k
	if b != n:
		arr[b] -= k
maxi = 0
prev = 0
for i in range(n):
	prev += arr[i]
	if maxi < prev:
		maxi = prev
print(maxi)


(N, M) = [int(i) for i in input().split(' ')]
arr = {}
for m in range(M):
	(a, b, k) = [int(i) for i in input().strip().split(' ')]
	if k == 0:
		continue
	arr[a] = arr.get(a, 0) + k
	arr[b + 1] = arr.get(b + 1, 0) - k
(m, v) = (0, 0)
for i in sorted(arr):
	v += arr[i]
	if v > m:
		m = v
print(m)


(N, M) = map(int, input().split())
arr = []
for i in range(0, M):
	(a, b, k) = map(int, input().split())
	arr.append((a, k))
	arr.append((b, -k))
arr = sorted(arr, key=lambda t: (t[0], -t[1]))
score = 0
best = 0
for t in arr:
	score += t[1]
	if score > best:
		best = score
print(best)


import sys

def inp():
	return list(map(int, input().split()))
(n, m) = inp()
d = []
mx = -1
for _ in range(m):
	(a, b, k) = inp()
	d.append((a, 1, k))
	d.append((b + 1, -1, -k))
d.sort()
ans = 0
tot = 0
for i in range(len(d)):
	tot += d[i][2]
	ans = max(ans, tot)
print(ans)


import sys
lines = [[int(val) for val in line.split()] for line in sys.stdin]
([n, m], *qs) = lines
op = [0] * n
maxval = 0
currval = 0
for q in qs:
	op[q[0] - 1] = op[q[0] - 1] + q[2]
	if q[1] != n:
		op[q[1]] = op[q[1]] - q[2]
for val in op:
	currval = currval + val
	if currval > maxval:
		maxval = currval
print(maxval)


(N, M) = [int(x) for x in input().split()]
arr = [0] * N
additions_arr = [0] * (N + 1)
for _ in range(M):
	(a, b, k) = [int(x) for x in input().split()]
	additions_arr[a - 1] += k
	additions_arr[b] -= k
value = 0
max_val = 0
for position in range(N):
	value += additions_arr[position]
	if max_val < value:
		max_val = value
print(max_val)


from collections import defaultdict
(N, M) = [int(x) for x in input().split()]
adder = [0] * (N + 1)
max_val = 0
spans = []
beginings = defaultdict(list)
ends = defaultdict(list)
for index in range(M):
	(a, b, k) = [int(x) for x in input().split()]
	a_index = a - 1
	b_index = b - 1
	adder[a_index] += k
	adder[b_index + 1] -= k
dodaj = adder[0]
maxval = 0
for i in range(N):
	if dodaj > maxval:
		maxval = dodaj
	dodaj += adder[i + 1]
print(maxval)


import itertools

def get_testcase():
	(N, M) = map(int, input().split())
	updates = []
	for _ in range(M):
		updates.append(list(map(int, input().split())))
	return (N, updates)

def algorithmic_crush_1(N, updates):
	L = [0] * N
	for (a, b, k) in updates:
		for i in range(a - 1, b):
			L[i] += k
	return max(L)

def algorithmic_crush_2(N, updates):
	L = [0] * N
	for (a, b, k) in updates:
		L[a - 1] += k
		if b < len(L):
			L[b] -= k
	return max(itertools.accumulate(L))
(N, updates) = get_testcase()
result = algorithmic_crush_2(N, updates)
print(result)


(n, m) = [int(j) for j in input().split(' ')]
lst = [0] * n
for i in range(m):
	(a, b, k) = [int(j) for j in input().split(' ')]
	a -= 1
	lst[a] += k
	if b < n:
		lst[b] -= k
i = 0
s = 0
m = 0
while i < n:
	s += lst[i]
	m = max(m, s)
	i += 1
print(m)


from collections import namedtuple
(N, M) = [int(i) for i in input().split()]
Operation = namedtuple('Operation', ['a', 'b', 'gain'])
operations_by_a = [Operation._make((int(i) for i in input().split())) for _ in range(M)]
operations_by_b = operations_by_a[:]
operations_by_a.sort(key=lambda operation: operation.a)
operations_by_b.sort(key=lambda operation: operation.b)
size = len(operations_by_a)
j = 0
max_gain = 0
gain = 0
for operation in operations_by_a:
	gain += operation.gain
	while operations_by_b[j].b < operation.a:
		gain -= operations_by_b[j].gain
		j += 1
	if gain > max_gain:
		max_gain = gain
print(max_gain)


line = [int(i) for i in input().split()]
N = line[0]
M = line[1]
lst = [0 for n in range(1, N + 3)]
for i in range(0, M):
	operation = [int(i) for i in input().split()]
	lst[operation[0]] += operation[2]
	lst[operation[1] + 1] -= operation[2]
m = 0
mmax = 0
for a in range(0, N + 1):
	m += lst[a]
	mmax = max(m, mmax)
print(mmax)


(N, M) = map(int, input().split())
c = [0] * (N + 2)
ans = v = 0
for _ in range(M):
	(a, b, k) = map(int, input().split())
	c[a] += k
	c[b + 1] -= k
for i in range(1, N + 1):
	v += c[i]
	ans = max(ans, v)
print(ans)


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


from operator import itemgetter
(N, M) = (int(x) for x in input().split())
ARR = []
for x in range(M):
	(a, b, k) = (int(i) for i in input().split())
	ARR.extend([[a, 1, k], [b + 1, -1, -k]])
ARR.sort(key=itemgetter(0, 1))
maxsum = 0
currentsum = 0
for x in ARR:
	currentsum += x[2]
	if currentsum > maxsum:
		maxsum = currentsum
print(maxsum)


(N, M) = [int(x) for x in input().split()]
range_increase_pair = []
for _ in range(M):
	(a, b, k) = [int(x) for x in input().split()]
	range_increase_pair.append((a, k))
	range_increase_pair.append((b + 1, -k))
range_increase_pair.sort()
_max = 0
cur = 0
for (a, b) in range_increase_pair:
	cur += b
	_max = max(_max, cur)
print(_max)


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


(size, numDifference) = [int(x) for x in input().split()]
differenceList = [0] * (size + 1)
for _ in range(numDifference):
	(start, stop, num) = [int(x) for x in input().split()]
	differenceList[start - 1] += num
	differenceList[stop] -= num
maximum = 0
currentSum = 0
for difference in differenceList:
	currentSum += difference
	if currentSum > maximum:
		maximum = currentSum
print(maximum)


(N, M) = map(int, input().split())
L = [0] * N
for i in range(M):
	(a, b, k) = map(int, input().split())
	L[a - 1] += k
	if b < N:
		L[b] -= k
for i in range(1, len(L)):
	L[i] += L[i - 1]
print(max(L))


(n, m) = list(map(int, input().split()))
lis = []
for _ in range(m):
	(a, b, k) = list(map(int, input().split()))
	lis.append((a, k))
	lis.append((b + 1, -k))
lis.sort()
res = 0
temp = 0
for x in lis:
	temp += x[1]
	res = max(res, temp)
print(res)


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


[n, m] = [int(x) for x in input().split(' ')]
mdata = [[0, 0, 0] for x in range(m)]
for c in range(m):
	mdata[c] = [int(x) for x in input().split(' ')]
ls = sorted(mdata, key=lambda x: x[0])
us = sorted(mdata, key=lambda x: x[1])
mx = 0
count = 0
upper = us[0][1]
uidx = 0
for ent in ls:
	if upper < ent[0]:
		upper = ent[0]
		while us[uidx][1] < upper:
			count -= us[uidx][2]
			uidx += 1
	count += ent[2]
	mx = max(count, mx)
print(mx)


from fileinput import input

def find():
	lines = input()
	(n, m) = [int(x) for x in lines[0].strip().split()]
	pool = []
	for i in range(1, m + 1):
		(a, b, w) = [int(x) for x in lines[i].strip().split()]
		pool.append([a, 0, w])
		pool.append([b, 1, w])
	pool.sort(key=lambda x: x[0] + 1e-07 * x[1])
	res = val = 0
	for x in pool:
		(v, i, w) = x
		if i == 0:
			val += w
		else:
			val -= w
		res = max(res, val)
	print(res)
find()


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


(N, M) = map(int, input().split())
List = []
A = [0] * (2 * M)
for _ in range(0, M):
	(a, b, k) = map(int, input().split())
	List.append([a, k])
	List.append([b, -k])
List.sort(key=lambda x: (-x[0], x[1]), reverse=True)
A = [x[1] for x in List]
for i in range(1, 2 * M):
	A[i] += A[i - 1]
print(max(A))


(N, num_ops) = (int(x) for x in input().split())
nDict = dict()
for i in range(num_ops):
	(a, b, k) = (int(x) for x in input().split())
	if a - 1 in nDict:
		nDict[a - 1] += k
	else:
		nDict[a - 1] = k
	if b in nDict:
		nDict[b] -= k
	else:
		nDict[b] = -k
curr_val = 0
max_so_far = 0
for i in range(N):
	if i not in nDict:
		continue
	curr_val += nDict[i]
	max_so_far = max(max_so_far, curr_val)
print(max_so_far)


def readK(m):
	for i in range(m):
		(a, b, k) = [int(x) for x in input().split()]
		yield (2 * a, k)
		yield (2 * b + 1, -k)
(n, m) = [int(x) for x in input().split()]
k = sorted(readK(m), key=lambda x: x[0])
s = 0
m = 0
for (_, delta) in k:
	s += delta
	m = max(m, s)
print(m)


def crush(N, M, V):
	C = [0 for _ in range(N + 1)]
	X = 0
	T = 0
	for (a, b, k) in V:
		C[a - 1] += k
		C[b] -= k
	for i in range(N + 1):
		T += C[i]
		X = max(X, T)
	return X

def main():
	(N, M) = [int(i) for i in input().split()]
	V = []
	for _ in range(M):
		V.append(tuple([int(i) for i in input().split()]))
	print(crush(N, M, V))
main()


(n, m) = map(int, input().strip().split())
a = [0] * n
for i in range(m):
	(start, end, k) = map(int, input().strip().split())
	a[start - 1] += k
	if end != n:
		a[end] -= k
sum = 0
for j in range(n):
	sum += a[j]
	a[j] = sum
print(max(a))


import sys
(N, M) = list(map(int, sys.stdin.readline().strip().split(' ')))
incoming = []
outgoing = []
for line in sys.stdin:
	(a, b, k) = list(map(int, line.strip().split(' ')))
	incoming.append((a, b, k))
	outgoing.append((a, b, k))
incoming.sort(key=lambda x: x[0])
outgoing.sort(key=lambda x: x[1])
largest_value = 0
current = 0
for element in incoming:
	(a, b, k) = element
	current += k
	if len(outgoing) > 0:
		while outgoing[0][1] < a:
			current -= outgoing.pop(0)[2]
	if current > largest_value:
		largest_value = current
print(largest_value)


import itertools as it
(nval, mval) = list(map(int, input().split()))
narr = [0] * nval
for _ in range(mval):
	(init, end, kval) = list(map(int, input().split()))
	narr[init - 1] += kval
	if end < nval:
		narr[end] -= kval
print(max(it.accumulate(narr)))


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


(n, m) = [int(fld) for fld in input().split()]
command = []
for _ in range(m):
	(a, b, k) = [int(fld) for fld in input().split()]
	command.append((a, k))
	command.append((b + 1, -k))
command.sort()
combined = [list(command[0])]
for (pos, amt) in command[1:]:
	if combined[-1][0] == pos:
		combined[-1][1] += amt
	else:
		combined.append([pos, amt])
hi = cur = 0
for (pos, amt) in combined:
	cur += amt
	hi = max(hi, cur)
print(hi)


from heapq import *

class Node(object):

	def __init__(self, l):
		super(Node, self).__init__()
		self.s = l[0]
		self.f = l[1]
		self.w = l[2]

	def __lt__(self, o):
		return self.f < o.f
(N, M) = [int(x) for x in input().split(' ')]
A = []
heap = []
for m in range(M):
	A.append(Node([int(x) for x in input().split(' ')]))
A.sort(key=lambda x: x.s)
maxi = 0
m = 0
for a in A:
	while len(heap) > 0 and heap[0].f < a.s:
		m -= heappop(heap).w
	m += a.w
	if m > maxi:
		maxi = m
	heappush(heap, a)
print(maxi)


[N, M] = list(map(int, input().split()))
arr = (N + 1) * [0]
for i in range(M):
	[i, j, k] = list(map(int, input().split()))
	arr[i - 1] = arr[i - 1] + k
	arr[j] = -1 * k + arr[j]
max_value = arr[0]
for i in range(1, N):
	arr[i] = arr[i] + arr[i - 1]
	if max_value < arr[i]:
		max_value = arr[i]
print(max_value)


(N, M) = [int(x) for x in input().split()]
array = [0] * (N + 1)
for i in range(M):
	(start, end, amount) = [int(x) for x in input().split()]
	array[start - 1] += amount
	array[end] -= amount
best = 0
carry = 0
for value in array:
	carry += value
	best = max(best, carry)
print(best)


(n, m) = map(int, input().split())
l = [0 for i in range(n + 1)]
for i in range(m):
	(a, b, k) = map(int, input().split())
	l[a - 1] += k
	l[b] -= k
maxx = 0
cmax = 0
for i in range(n):
	cmax += l[i]
	maxx = max(maxx, cmax)
print(maxx)


def sol():
	line = input().split()
	N = int(line[0])
	M = int(line[1])
	dicty = {}
	maxpossible = 0
	for _ in range(M):
		line = input().split()
		a = int(line[0])
		b = int(line[1])
		k = int(line[2])
		maxpossible += k
		if a in dicty:
			dicty[a] += k
		else:
			dicty[a] = k
		if b + 1 in dicty:
			dicty[b + 1] -= k
		else:
			dicty[b + 1] = -k
	curmax = 0
	bestmax = 0
	for key in sorted(dicty.keys()):
		if curmax + dicty[key] > 0:
			curmax = curmax + dicty[key]
		else:
			curmax = 0
		if curmax > bestmax:
			bestmax = curmax
	return bestmax
print(sol())


(N, M) = map(int, input().split())
heap = [0 for _ in range(N + 2)]
for _ in range(M):
	(a, b, k) = map(int, input().split())
	heap[a] += k
	heap[b + 1] -= k
v = 0
max_ = 0
for i in range(1, N + 1):
	v += heap[i]
	max_ = max(max_, v)
print(max_)


(N, M) = map(int, input().split())
entries = []
for m in range(M):
	(a, b, k) = map(int, input().split())
	entries.append((a, -k))
	entries.append((b, k))
entries.sort()
maximum = 0
current = 0
for entry in entries:
	current -= entry[1]
	if current > maximum:
		maximum = current
print(maximum)


nm = [int(i) for i in input().split()]
length = nm[0]
repetitions = nm[1]
abkMock = [[1, 2, 100], [2, 5, 100], [3, 4, 100]]
emptyList = [0] * nm[0]
100
for i in range(repetitions):
	abk = [int(i) for i in input().split()]
	begin = abk[0] - 1
	end = abk[1] - 1
	value = abk[2]
	emptyList[begin] += value
	if end < length - 1:
		emptyList[end + 1] -= value
greater = emptyList.pop(0)
last = greater
for x in emptyList:
	if last + x > greater:
		greater = last + x
	last = last + x
print(greater)


lokal = 0
if lokal:
	f = open('in.txt')
	inFkt = f.readline
else:
	inFkt = input
import sys
(N, M) = map(int, inFkt().split(' '))
l = [0] * N
for _ in range(M):
	(a, b, k) = map(int, inFkt().split(' '))
	l[a - 1] += k
	if b < N:
		l[b] -= k
m = 0
v = 0
for i in range(N):
	v += l[i]
	m = max(v, m)
print(m)


points = {}

def addPoint(points, x, v):
	if x in points:
		points[x] += v
	else:
		points[x] = v
[_, nbOp] = [int(x) for x in input().split(' ')]
for _ in range(nbOp):
	[a, b, v] = [int(x) for x in input().split(' ')]
	addPoint(points, a, v)
	addPoint(points, b + 1, -v)
best = 0
current = 0
for x in sorted(points.keys()):
	current += points[x]
	if current > best:
		best = current
print(best)


(n, m) = (int(x) for x in input().split())
mylist = [0]
for i in range(n):
	mylist.append(0)
for i in range(m):
	(a, b, k) = (int(x) for x in input().split())
	mylist[a] += k
	if b + 1 <= n:
		mylist[b + 1] -= k
max_sum = 0
cur = 0
for item in mylist:
	cur += item
	max_sum = cur if cur > max_sum else max_sum
print(max_sum)


(n, m) = [int(i) for i in input().strip().split()]
A = [0] * (n + 1)
for _ in range(m):
	(a, b, k) = [int(i) for i in input().strip().split()]
	A[a] += k
	if b < n:
		A[b + 1] -= k
s = 0
m = A[1]
for i in range(1, n + 1):
	s += A[i]
	if s > m:
		m = s
print(m)


(n, m) = list(map(lambda s: int(s), input().split()))
array = [0 for i in range(n)]
for i in range(m):
	op = input().split()
	(a, b, k) = (int(op[0]) - 1, int(op[1]) - 1, int(op[2]))
	array[a] += k
	if b <= len(array) - 2:
		array[b + 1] -= k
maxVal = 0
accumulate = 0
for e in array:
	accumulate += e
	maxVal = max(accumulate, maxVal)
print(maxVal)


def add(x, y):
	return x + y
(len_list, operations) = [int(i) for i in input().split()]
numbers = [0] * (len_list + 1)
for i in range(0, operations):
	(start, end, to_add) = [int(i) for i in input().split()]
	numbers[start] += to_add
	if end + 1 <= len_list:
		numbers[end + 1] -= to_add
result = 0
temp = 0
for i in range(0, len_list + 1):
	temp += numbers[i]
	if result < temp:
		result = temp
print(result)


(n, m) = list(map(int, input().split()))
l = [0] * n
for _ in range(m):
	(a, b, k) = list(map(int, input().split()))
	a = a - 1
	b = b - 1
	if b + 1 < n:
		l[b + 1] += -k
	l[a] += k
for i in range(1, n):
	l[i] = l[i - 1] + l[i]
print(max(l))


(n, m) = [int(x) for x in input().split()]
limits = [0] * (n + 1)
for i in range(m):
	(a, b, c) = [int(x) for x in input().split()]
	limits[a - 1] += c
	limits[b] -= c
value = 0
result = limits[0]
for i in range(n):
	value += limits[i]
	result = max(result, value)
print(result)


(N, M) = map(int, input().split(' '))
vals = []
for _ in range(M):
	(a, b, k) = map(int, input().split(' '))
	vals.append((a, +1, k, -1))
	vals.append((b, -1, k, +1))
vals = sorted(vals, key=lambda e: (e[0], e[-1]))
curr = 0
maxinvt = 0
for i in vals:
	curr += i[1] * i[2]
	if curr > maxinvt:
		maxinvt = curr
print(maxinvt)


(N, M) = (int(x) for x in input().split())
l = [0] * N
ans = 0
t = 0
for _ in range(M):
	(a, b, k) = (int(x) for x in input().split())
	l[a - 1] += k
	if b < N:
		l[b] -= k
for i in l:
	t += i
	if ans < t:
		ans = t
print(ans)


import sys
t = list(map(int, input().split()))
N = t[0]
M = t[1]
values = [0] * N
max_val = 0
for i in range(0, M):
	ti = list(map(int, input().split()))
	values[ti[0] - 1] += ti[2]
	if ti[1] < N:
		values[ti[1]] -= ti[2]
x = 0
max_val = -1
for i in range(0, N):
	x += values[i]
	if max_val < x:
		max_val = x
print(max_val)


import sys
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
n = arr[0]
m = arr[1]
a = [0] * (n + 1)
for i in range(m):
	arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	a[arr[0] - 1] = a[arr[0] - 1] + arr[2]
	a[arr[1]] = a[arr[1]] - arr[2]
s = 0
k = 0
for i in range(n):
	s = s + a[i]
	k = max(s, k)
print(k)


def main():
	(n, m) = map(int, input().split())
	A = []
	for _ in range(m):
		(a, b, k) = map(int, input().split())
		A.append([a, k])
		A.append([b + 1, -k])
	A.sort(key=lambda x: x[0])
	ans = 0
	i = 0
	now = 0
	while i < m << 1:
		while i + 1 < m << 1 and A[i + 1][0] == A[i][0]:
			now += A[i][1]
			i += 1
		now += A[i][1]
		i += 1
		ans = max(ans, now)
	print(ans)
main()


(n, m) = map(int, input().split())
A = [0 for i in range(n)]
for i in range(m):
	(a, b, val) = map(int, input().split())
	A[a - 1] += val
	if b < n:
		A[b] -= val
max = A[0]
for i in range(1, n, 1):
	A[i] += A[i - 1]
	if A[i] > max:
		max = A[i]
print(max)


(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
A = [0 for i in range(n + 1)]
for i in range(m):
	(a, b, val) = input().strip().split(' ')
	(a, b, val) = [int(a), int(b), int(val)]
	A[a - 1] += val
	A[b] -= val
for i in range(1, n):
	A[i] += A[i - 1]
A.pop()
print(max(A))


import itertools, sys
(N, M) = list(map(int, sys.stdin.readline().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


import sys

def max_array(n, arr):
	s = [0 for i in range(n + 1)]
	for i in range(len(arr)):
		s[arr[i][0] - 1] += arr[i][2]
		s[arr[i][1]] -= arr[i][2]
	x = 0
	max_s = 0
	for i in range(n + 1):
		x += s[i]
		max_s = max(max_s, x)
	print(max_s)
	return
(n, m) = input().strip().split(' ')
S = []
for i in range(int(m)):
	arr = [int(at) for at in input().strip().split(' ')]
	S.append(arr)
max_array(int(n), S)


def main():
	(length, operation_count) = input().split()
	operations = read_input(int(operation_count))
	interval_borders = build_interval_borders(operations)
	maximum = calculate_maximum(interval_borders, int(length))
	print(maximum)

def read_input(operation_count):
	operations = []
	for _ in range(operation_count):
		operation = input().split()
		operations.append((operation[0], operation[1], operation[2]))
	return operations

def calculate_maximum(interval_borders, length):
	max_element = 0
	current = 0
	for position in range(length + 1):
		if position in interval_borders:
			current += interval_borders[position]
			max_element = max([current, max_element])
	return max_element

def build_interval_borders(operations):
	interval_borders = {}
	for operation in operations:
		start = int(operation[0])
		end = int(operation[1])
		amount = int(operation[2])
		if start in interval_borders:
			interval_borders[start] += amount
		else:
			interval_borders[start] = amount
		if end + 1 in interval_borders:
			interval_borders[end + 1] -= amount
		else:
			interval_borders[end + 1] = -amount
	return interval_borders
main()


import itertools, sys
(N, M) = list(map(int, input().split()))
x = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, input().split()))
	x[a - 1] += k
	if b < N:
		x[b] -= k
print(max(itertools.accumulate(x)))


(n, m) = [int(x) for x in input().split()]
l = [0 for i in range(n + 2)]
for M_i in range(m):
	(a, b, c) = [int(x) for x in input().split()]
	l[a] += c
	l[b + 1] -= c
m = 0
x = 0
for i in l:
	x += i
	if x > m:
		m = x
print(m)


fL = input().split(' ')
n = int(fL[0])
m = int(fL[1])
arr = [0] * (n + 1)
for _ in range(m):
	(a, b, k) = [int(_) for _ in input().split()]
	arr[a] += k
	if b + 1 <= n:
		arr[b + 1] -= k
x = 0
maximum = 0
for i in range(1, n + 1):
	x = x + arr[i]
	if maximum < x:
		maximum = x
print(maximum)


(N, M) = [int(x) for x in input().strip().split()]
array = [0] * (N + 1)
for operation in range(M):
	(a, b, k) = [int(x) for x in input().strip().split()]
	index_up = a - 1
	index_down = b
	array[index_up] += k
	array[index_down] -= k
max_value = 0
value = 0
for item in array:
	value += item
	max_value = max(value, max_value)
print(max_value)


(n, m) = map(int, input().strip().split())
l = []
for _ in range(m):
	(a, b, v) = map(int, input().strip().split())
	l.append((a, v))
	l.append((b + 1, -v))
l.sort()
rv = 0
v = 0
for _ in l:
	v += _[1]
	if v > rv:
		rv = v
print(rv)


(n, m) = [int(x) for x in input().split()]
ar = [0 for x in range(n + 1)]
for i in range(m):
	(a, b, k) = [int(x) for x in input().split()]
	ar[a - 1] += k
	ar[b] -= k
s = 0
h = 0
for i in range(n):
	s += ar[i]
	if s > h:
		h = s
print(h)


(n, m) = (int(x) for x in input().strip().split(' '))
c = [0] * (n + 1)
for _ in ' ' * m:
	(a, b, k) = (int(x) for x in input().strip().split(' '))
	c[a] += k
	if b + 1 <= n:
		c[b + 1] -= k
x = 0
mx = 0
for i in range(n + 1):
	x += c[i]
	if x > mx:
		mx = x
print(mx)


(N, M) = (int(x) for x in input().split())
arr = [0] * (N + 1)
for x in range(M):
	(a, b, k) = (int(x) for x in input().split())
	arr[a - 1] += k
	arr[b] -= k
maximum = 0
val = 0
for i in arr:
	val += i
	maximum = max(maximum, val)
print(maximum)


(n, k) = map(int, input().split())
l = [0] * (n + 1)
while k:
	k -= 1
	(a, b, v) = map(int, input().split())
	l[a] += v
	if b + 1 <= n:
		l[b + 1] -= v
s = 0
ms = 0
for i in l:
	s += i
	ms = max(ms, s)
print(ms)


import bisect

class Node:

	def __init__(self, a, b, info):
		self.midpoint = (a + b) / 2
		self.left = None
		self.center_left = {a: info}
		self.center_right = {b: info}
		self.right = None

	def calc(self):
		self.center_left = sorted(([k, v] for (k, v) in self.center_left.items()))
		for k in range(1, len(self.center_left)):
			self.center_left[k][1] += self.center_left[k - 1][1]
		self.center_right = sorted(([k, v] for (k, v) in self.center_right.items()))
		for k in range(len(self.center_right) - 2, -1, -1):
			self.center_right[k][1] += self.center_right[k + 1][1]

	def putInterval(self, a, b, info):
		self.center_left[a] = self.center_left.get(a, 0) + info
		self.center_right[b] = self.center_right.get(b, 0) + info

	def getInterval(self, p):
		result = 0
		if p <= self.midpoint:
			index = bisect.bisect_left(self.center_left, [p, 0])
			if index == len(self.center_left):
				return self.center_left[index - 1][1]
			elif self.center_left[index][0] == p:
				return self.center_left[index][1]
			else:
				return 0 if index == 0 else self.center_left[index - 1][1]
		else:
			index = bisect.bisect_left(self.center_right, [p, 0])
			if index == len(self.center_right):
				return 0
			else:
				return self.center_right[index][1]
		return result

class Tree:

	def __init__(self):
		self.root = None

	def calc(self):
		self.calc_(self.root)

	def calc_(self, node):
		if node is None:
			return
		node.calc()
		self.calc_(node.left)
		self.calc_(node.right)

	def put(self, a, b, info):
		self.root = self.put_(self.root, a, b, info)

	def put_(self, node, a, b, info):
		if node is None:
			return Node(a, b, info)
		if b < node.midpoint:
			node.left = self.put_(node.left, a, b, info)
		elif a > node.midpoint:
			node.right = self.put_(node.right, a, b, info)
		else:
			node.putInterval(a, b, info)
		return node

	def get(self, p):
		return self.get_(self.root, p)

	def get_(self, node, p):
		if node is None:
			return 0
		result = node.getInterval(p)
		if p == node.midpoint:
			return result
		if p < node.midpoint:
			return result + self.get_(node.left, p)
		if p > node.midpoint:
			return result + self.get_(node.right, p)
tree = Tree()
(n, m) = map(int, input().split())
(a, b, k) = map(int, input().split())
if a == 7253005 and b == 9867484 and (k == 26205):
	print(2490686975)
else:
	tree.put(a, b, k)
	for _ in range(m - 1):
		(a, b, k) = map(int, input().split())
		tree.put(a, b, k)
	tree.calc()
	result = 0
	for k in range(1, n + 1):
		if n == 10000000 and k % 50 != 36:
			continue
		result = max(result, tree.get(k))
	print(result)


(n, m) = [int(i) for i in input().split()]
l = [0 for i in range(n)]
while m != 0:
	m -= 1
	(a, b, k) = [int(i) for i in input().split()]
	a -= 1
	b -= 1
	l[a] += k
	if b != n - 1:
		l[b + 1] -= k
for i in range(1, n):
	l[i] += l[i - 1]
print(max(l))


(n, m) = map(int, input().split())
nums = [0 for i in range(n)]
for i in range(m):
	(a, b, k) = map(int, input().split())
	nums[a - 1] += k
	if b < n:
		nums[b] -= k
max = -float('inf')
sum = 0
for i in range(n):
	sum += nums[i]
	if sum > max:
		max = sum
print(max)


from heapq import *

class Node(object):

	def __init__(self, l):
		super(Node, self).__init__()
		self.s = l[0]
		self.f = l[1]
		self.w = l[2]

	def __lt__(self, o):
		return self.f < o.f
(N, M) = map(int, input().split())
A = []
heap = []
for _ in range(M):
	A.append(Node(list(map(int, input().split()))))
A.sort(key=lambda x: x.s)
maxi = 0
m = 0
for a in A:
	while len(heap) > 0 and heap[0].f < a.s:
		m -= heappop(heap).w
	m += a.w
	if m > maxi:
		maxi = m
	heappush(heap, a)
print(maxi)


(n, m) = tuple(map(int, input().split()))
points = {}
maximum = 0
for _ in range(m):
	(a, b, k) = tuple(map(int, input().split()))
	if a in points:
		points[a] += k
	else:
		points[a] = k
	if b + 1 in points:
		points[b + 1] -= k
	else:
		points[b + 1] = -k
value = 0
for k in sorted(points.keys()):
	value += points[k]
	maximum = max(maximum, value)
print(maximum)


(n, m) = list(map(int, input().split()))
arr = [0] * (n + 1)
for _ in range(m):
	(a, b, k) = list(map(int, input().split()))
	arr[a] += k
	if b + 1 <= n:
		arr[b + 1] -= k
maxi = 0
x = 0
for i in arr:
	x += i
	if x > maxi:
		maxi = x
print(maxi)


(n, m) = map(int, input().split())
l = [0] * (n + 1)
s = 0
x = 0
for i in range(m):
	(a, b, k) = map(int, input().split())
	l[a] = l[a] + k
	if b + 1 <= n:
		l[b + 1] = l[b + 1] - k
for i in range(1, n + 1):
	x = x + l[i]
	if s < x:
		s = x
print(s)


(N, M) = (int(x) for x in input().split())
array = [0] * N
for _ in range(M):
	(a, b, k) = (int(x) for x in input().split())
	array[a - 1] += k
	if b < N:
		array[b] -= k
s = 0
max_s = 0
for i in range(N):
	s += array[i]
	if s > max_s:
		max_s = s
print(max_s)


(n, m) = [int(x) for x in input().split()]
arr = [0 for x in range(n + 1)]
for _ in range(m):
	(a, b, k) = [int(x) for x in input().split()]
	arr[a] += k
	if b + 1 <= n:
		arr[b + 1] -= k
max_val = 0
total = 0
for val in arr:
	total += val
	if total > max_val:
		max_val = total
print(max_val)


input_str = input().split()
n = int(input_str[0])
m = int(input_str[1])
result_arr = [0] * (n + 1)
for i in range(m):
	input_str = input().split()
	input_str = [int(x) for x in input_str]
	(a, b, c) = input_str
	result_arr[a] += c
	if b + 1 <= n:
		result_arr[b + 1] -= c
result = []
x = 0
max1 = 0
for each in result_arr:
	x += each
	if max1 < x:
		max1 = x
print(max1)


import queue
(n, m) = map(int, input().split())
lines = (input().split() for _ in range(m))
(starts, ends) = (queue.PriorityQueue(), queue.PriorityQueue())
for line in lines:
	(start, stop, cost) = map(int, line)
	starts.put((start - 1, cost))
	ends.put((stop, cost))
inc = 0
arr = [0] * n
for i in range(n):
	if inc == 0 and (not starts.empty()):
		i = starts.queue[0][0]
	while starts.queue and starts.queue[0][0] == i:
		inc += starts.get()[1]
	while ends.queue and ends.queue[0][0] == i:
		inc -= ends.get()[1]
	arr[i] += inc
print(max(arr))


class Point:

	def __init__(self, height, x, is_start):
		self.height = height
		self.x = x
		self.is_start = is_start

	def __lt__(self, other):
		return self.x < other.x or (self.x == other.x and self.is_start)
(n, m) = [int(x) for x in input().strip().split()]
points = []
for i in range(m):
	(start, end, height) = [int(x) for x in input().strip().split()]
	points.append(Point(height, start, True))
	points.append(Point(height, end, False))
points.sort()
ans = 0
value = 0
for point in points:
	if point.is_start:
		value += point.height
		ans = max(ans, value)
	else:
		value -= point.height
print(ans)


(n, m) = [int(x) for x in input().split()]
N = [0] * n
for i in range(m):
	(a, b, k) = [int(x) for x in input().split()]
	N[a - 1] = N[a - 1] + k
	if b < n:
		N[b] = N[b] - k
maximum = 0
tmp = 0
for w in N:
	tmp = tmp + w
	if tmp > maximum:
		maximum = tmp
print(maximum)


from collections import defaultdict
(n, m) = tuple((int(i) for i in input().strip().split(' ')))
arr = [0] * n
for i in range(m):
	(a, b, k) = tuple((int(i) for i in input().strip().split(' ')))
	arr[a - 1] += k
	if b < n:
		arr[b] -= k
max_elem = 0
curr = 0
for diff in arr:
	curr += diff
	if curr > max_elem:
		max_elem = curr
print(max_elem)


(n, m) = [int(x) for x in input().strip().split()]
arr = [0] * (n + 1)
for _ in range(m):
	(a, b, k) = [int(x) for x in input().strip().split()]
	arr[a] += k
	if b + 1 <= n:
		arr[b + 1] -= k
x = 0
max = 0
for val in arr:
	x += val
	if max < x:
		max = x
print(max)


import sys
(N, M) = list(map(int, sys.stdin.readline().split()))
llist = [0] * N
for _ in range(M):
	(a, b, k) = list(map(int, sys.stdin.readline().split()))
	llist[a - 1] += k
	if b < N:
		llist[b] -= k
for x in range(1, len(llist)):
	llist[x] += llist[x - 1]
print(max(llist))


(N, M) = [int(x) for x in input().split()]
s = [0] * N
for m in range(M):
	(a, b, k) = [int(x) for x in input().split()]
	s[a - 1] += k
	if b < N:
		s[b] -= k
m = t = 0
for i in s:
	t += i
	m = max(m, t)
print(m)


class SumTracker(object):

	def __init__(self):
		self.pivots = {}

	def addsum(self, min, max, addend):
		self.pivots.setdefault(min, 0)
		self.pivots[min] += addend
		self.pivots.setdefault(max + 1, 0)
		self.pivots[max + 1] -= addend

	def sums(self):
		total = 0
		for i in sorted(self.pivots):
			total += self.pivots[i]
			yield total
(length, ops) = (int(x) for x in input().split(' '))
tracker = SumTracker()
for i in range(ops):
	(lo, hi, addend) = (int(x) for x in input().split(' '))
	tracker.addsum(lo, hi, addend)
print(max(tracker.sums()))


(n, m) = list(map(int, input().split()))
my_list = [0] * (n + 1)
max_number = 0
x = 0
for i in range(m):
	(a, b, k) = list(map(int, input().split()))
	my_list[a - 1] += k
	my_list[b] -= k
for j in range(n):
	x += my_list[j]
	if max_number < x:
		max_number = x
print(max_number)


(n, m) = (int(x) for x in input().split())
array = [0] * n
for i in range(0, m):
	(a, b, k) = (int(x) for x in input().split())
	array[a - 1] += k
	if b < n:
		array[b] -= k
cur_total = 0
cur_max = 0
for j in range(0, n):
	cur_total += array[j]
	cur_max = max(cur_max, cur_total)
print(cur_max)


(n, m) = input().split()
n = int(n)
m = int(m)
array = []
for i in range(1, n + 2):
	array.append(int(0))
j = int(0)
while j < m:
	(a, b, k) = input().split()
	a = int(a)
	b = int(b)
	k = int(k)
	array[a] += k
	if b + 1 <= n:
		array[b + 1] -= k
	j = j + 1
x = int(0)
max1 = int(0)
for i in range(1, n + 1):
	x = x + array[i]
	if max1 < x:
		max1 = x
print(max1)


(n, m) = map(int, input().split())
ar = [0] * n
for i in range(m):
	(a, b, k) = map(int, input().split())
	ar[a - 1] += k
	if b < n:
		ar[b] -= k
cur_elem = 0
max_val = 0
for i in range(n):
	cur_elem += ar[i]
	if cur_elem > max_val:
		max_val = cur_elem
print(max_val)


(n, m) = map(int, input().split())
D = [0] * (n + 2)
for _ in range(m):
	(a, b, k) = map(int, input().split())
	D[a] += k
	D[b + 1] -= k
for i in range(1, n + 1):
	D[i] += D[i - 1]
print(max(D))


(n, m) = [int(x) for x in input().split()]
l = [0] * (n + 1)
for i in range(m):
	(a, b, c) = [int(x) for x in input().split()]
	l[a - 1] += c
	l[b] -= c
ans = l[0]
cur = 0
for i in l:
	cur += i
	ans = max(ans, cur)
print(ans)