Redirecting to
NADOS

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)
Input Format
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.
Output Format
print a single line containing one integer - the maximum possible number of Trees with height M.
Question Video
Constraints
Constraint : 
2<=N<=100000.
2<=Q<=100000.
1<=M1<=L<=R<=N.
Sample Input
10 3 2
2 6
4 9
1 4
Sample Output
3


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name