You are given a list of size N,
initialized with zeroes. You have to
perform M queries on the list and
output the maximum of final values of
all the N elements in the list. For
every query, you are given three
integers a, b and k and you have to
add value k to all the elements
ranging from index a to b(both
inclusive). Input Format First line
will contain two integers N and M
separated by a single space. Next M
lines will contain three integers a, b
and k separated by a single space.
Numbers in list are numbered from 1to
N. Output Format A single line
containing maximum value in the final
list.
Constraints: 3 <= N <= 10^7, 1 <= M <= 2 * 10^5, 1 <= a <= b <= N, 0 <= k <= 10^9
Sample Input:
5 3
1 2 100
2 5 100
3 4 100
Sample Output:
200
What can be the most efficient approach to solve this problem?