## Description

## 1Â Â Â Â Â Problem

You are given an array of *N *elements which are initialized to 0. You are given a sequence of *M *operations of the sort (*p,q,r*). The operation (*p,q,r*) signifies that the integer *r *should be added to all array elements *A*[*p*]*,A*[*p *+ 1]*,…,A*[*q*]. You are to output the maximum element in the array that would result from performing all *M *operations. There is a naive solution that simply performs all operations and then returns the maximum value, that takes *O*(*MN*) time. We are looking for a more efficient algorithm.

## 2Â Â Â Â Â Input

The first line will have two integers *N *and *M *separated by a space. The next *M *lines each have 3 integers separated by spaces. The input can be assumed to obey the following constraints:

3 â‰¤ *N *â‰¤ 10^{7}

1 â‰¤ *M *â‰¤ 2 âˆ— 10^{5}

1 â‰¤ *p *â‰¤ *q *â‰¤ *N*

0 â‰¤ *r *â‰¤ 10^{9}

**3Â Â Â Â Â Output**

The output should be a single line containing the required maximum value.

## 4Â Â Â Â Â Example

Sample Input

6 3

1 3 200 2 5 50

3 6 100

Sample Output

350

Explanation

The array has 6 elements initialized to 0, and there will be 3 operations.

After the first operation, the array would be [200*,*200*,*200*,*0*,*0*,*0].

After the second operation, the array would be [200*,*250*,*250*,*50*,*50*,*0].

After the third operation, the array would be [200*,*250*,*350*,*150*,*150*,*100]. So the required answer is the maximum value in the array, which is 350.

## 5Â Â Â Â Â Requirements

For the constraints given above, your program should run in 1 second. You must submit source code for a program written in C/C++/Java on the Electronic Assignment System. Some test cases will be provided on the course website. You can verify if your program works on the test cases before submitting.