Moksh And His Girlfriend
Recently Moksh(HR of Pepcoding) invented a serum which can increase height of plant by 1 unit. Moksh's girlfriend birthday is next month. He is planning something amazing as a gift for her.His girlfriend's favourite Integer is M. Initially Moksh has N (1 to N) no. of beautiful Rose plants, Each plant can have an Integer height,Initially the height of each plant is zero. Subhesh gives Moksh Q number of operations,In each operation Moksh got two integer start and end and he increases the height of all the plants between start and end position (including start and end) by 1. As Moksh wasn't happy with the pattern of height of the plants formed, He went to Rajneesh and asked him to remove any 1 operation from the Q operations such that the count of plants with height M is maximum possible. Output the maximum possible number of plants with height M. Expected Complexity : O(n+q)
Constraint : 2<=N<=100000. 2<=Q<=100000. 1<=M<Q. 1<=L<=R<=N.
First line contains three space separated integer N(no. of Rose plants), Q(number of operations), M. Each of the next Q lines contains two space-separated integers L and R describing one operation.
print a single line containing one integer - the maximum possible number of Trees with height M.
10 3 2 2 6 4 9 1 4