Problems
Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000 ), which, as always, are conveniently numbered from 1..N. Accordingly, he snapped M (1 <= M <= 100,000 ) photos, each covering a contiguous range of cows: photo i contains cows a_i through b_i inclusive. The photos collectively may not necessarily cover every single cow.
After taking his photos, FJ notices a very interesting phenomenon: each photo he took contains exactly one cow with spots! FJ was aware that he had some number of spotted cows in his herd, but he had never actually counted them. Based on his photos, please determine the maximum possible number of spotted cows that could exist in his herd. Output -1 if there is no possible assignment of spots to cows consistent with FJ's photographic results.
Input
Line 1: Two integers N and M.
Lines 2..M+1: Line i+1 contains a_i and b_i.
Output
Line 1: The maximum possible number of spotted cows on FJ's farm, or -1 if there is no possible solution.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | |
| #2 | 20 | |
| #3 | 30 | Impossible situations are not given |
| #4 | 40 | No additional restrictions |
Example #1
20 4
1 10
5 8
6 15
10 20
2
Example #2
10 3
3 4
6 8
1 10
-1
Example #3
20 4
3 10
5 8
6 12
10 16
8
Example #4
3 3
1 2
2 2
2 3
1
You must sign in to write code.