Liars

gistfile1.txt

You have N soldiers numbered from 1 to N. Each of your soldiers is either a liar or a truthful person. You have M sets of information about them. Each set of information tells you the number of liars among a certain range of your soldiers. Let L be the total number of your liar soldiers. Since you can’t find the exact value of L, you want to find the minimum and maximum value of L.

Input Format

The first line of the input contains two integers N and M.
Each of next M lines contains three integers:
A B C where the set of soldiers numbered as {A, A+1, A+2, …, B}, exactly C of them are liars. (1 <= Ai <= Bi <= n) and (0 <= Ci <= Bi-Ai).
Note: N and M are not more than 101, and it is guaranteed the given informations is satisfiable.

Output Format
Print two integers Lmin and Lmax to the output.

Sample Input #1

3 2

1 2 1

2 3 1

Sample Output #1

1 2

Sample Input #2

20 11

3 8 4

1 9 6

1 13 9

5 11 5

4 19 12

8 13 5

4 8 4

7 9 2

10 13 3

7 16 7

14 19 4

Sample Output #2

13 14

Explanation
In the first input, the initial line is “3 2”, i.e. that there are 3 soldiers and we have 2 sets of information. The next line says there is one liar in the set of soldiers {1, 2}. The final line says there is one liar in the set {2,3}. There are two possibilities for this scenario: Soldiers number 1 and 3 are liars or soldier number 2 is liar.
So the minimum number of liars is 1 and maximum number of liars is 2. Hence the answer, 1 2.