Chef has N Assistant in his restaurant. These Assistant are numbered from 1 to N.Everyday some of the assistant (from number x to y ) comes for work and get some feedback points (positive or negative) by guests.He either adds or subtracts a constant from the feedback-points. He performs M such operations for M days. Each operation is of the form: x y z where each of them is an integer. Chef has to add/subtract z to feedback-points of assistant_number from x to y (both inclusive). After doing this, Chef want to find the maximum feed-back points. Your task is to help Chef in finding the best performance by calculating maximum feedback-points.
First line of input contains a single integer T, the number of test cases.
Each test case starts with a line containing two space separated integers N, number of assistants and M.Then follow M lines. Each of these lines is of the form x y z. Each separated by a single space.
For each test case output a single line containing the maximum feedback-point after All modifications.
1 ≤ T ≤ 20
1 ≤ M ≤ 1000
1 ≤ N ≤ 1000000
1 ≤ x ≤ y ≤ N
-100000 ≤ z ≤ 100000
Input: 1 10 2 3 6 -4 5 9 1 Output: 9
Initially the feedback-points are as follows: 0 0 0 0 0 0 0 0 0 0. First operation decreases the feedback of assistant Number 3,4,5 and 6 by 4. Now, the feed-back points looks like: 0 0 -4 -4 -4 -4 0 0 0 0. The second operation increases the numbers of Assistant number 5 to 9 by 1. The feed-back points will now be 0 0 -4 -4 -3 -3 1 1 1 0. Thus, the maximum feedback-points is 1.
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions