Young Teodor enjoys drawing. His favourite hobby is drawing segments with integer borders inside his huge \[1;_m_\] segment. One day Teodor noticed that picture he just drawn has one interesting feature: there doesn't exist an integer point, that belongs each of segments in the picture. Having discovered this fact, Teodor decided to share it with Sasha.
Sasha knows that Teodor likes to show off so he never trusts him. Teodor wants to prove that he can be trusted sometimes, so he decided to convince Sasha that there is no such integer point in his picture, which belongs to each segment. However Teodor is lazy person and neither wills to tell Sasha all coordinates of segments' ends nor wills to tell him their amount, so he suggested Sasha to ask him series of questions 'Given the integer point _x__i_, how many segments in Fedya's picture contain that point?', promising to tell correct answers for this questions.
Both boys are very busy studying and don't have much time, so they ask you to find out how many questions can Sasha ask Teodor, that having only answers on his questions, Sasha can't be sure that Teodor isn't lying to him. Note that Sasha doesn't know amount of segments in Teodor's picture. Sure, Sasha is smart person and never asks about same point twice.
## Input
First line of input contains two integer numbers: _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100 000) — amount of segments of Teodor's picture and maximal coordinate of point that Sasha can ask about.
_i_th of next _n_ lines contains two integer numbers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _m_) — left and right ends of _i_th segment in the picture. Note that that left and right ends of segment can be the same point.
It is guaranteed that there is no integer point, that belongs to all segments.
## Output
Single line of output should contain one integer number _k_ – size of largest set (_x__i_, _cnt_(_x__i_)) where all _x__i_ are different, 1 ≤ _x__i_ ≤ _m_, and _cnt_(_x__i_) is amount of segments, containing point with coordinate _x__i_, such that one can't be sure that there doesn't exist point, belonging to all of segments in initial picture, if he knows only this set(and doesn't know _n_).
[samples]
## Note
First example shows situation where Sasha can never be sure that Teodor isn't lying to him, because even if one knows _cnt_(_x__i_) for each point in segment \[1;4\], he can't distinguish this case from situation Teodor has drawn whole \[1;4\] segment.
In second example Sasha can ask about 5 points e.g. 1, 2, 3, 5, 6, still not being sure if Teodor haven't lied to him. But once he knows information about all points in \[1;6\] segment, Sasha can be sure that Teodor haven't lied to him.
Let $ A = \{1, 2, \dots, m\} $ be the set of integer points.
Let $ f(x) $ denote the number of segments containing point $ x \in A $, for $ x = 1, 2, \dots, m $.
Given: There is **no** integer point that belongs to **all** $ n $ segments. That is, $ \forall x \in A, f(x) < n $.
Sasha observes a set of query-answer pairs $ \{(x_i, f(x_i))\} $, where all $ x_i $ are distinct and $ 1 \le x_i \le m $.
Sasha **cannot be sure** that Teodor is telling the truth (i.e., that no point lies in all segments) if there exists **some** assignment of $ n' $ segments (with $ n' $ unknown) consistent with the observed $ f(x_i) $ values, **but** in which **some** integer point $ x \in A $ is covered by **all** $ n' $ segments.
We are to find the **maximum size** $ k $ of a set $ S \subseteq A $ such that **even after observing** $ f(x) $ for all $ x \in S $, it is **still possible** that there exists a point covered by **all** segments (i.e., Teodor might be lying), **regardless of what $ n $ is**.
In other words: We want the largest subset $ S \subseteq \{1, \dots, m\} $ such that there exists **some** multiset of segments (with unknown number $ n' $) that:
1. Matches the observed $ f(x) $ for all $ x \in S $,
2. But **some** point $ x \in \{1, \dots, m\} $ is covered by **all** $ n' $ segments.
We are guaranteed that in the **true** configuration, **no** point is covered by all $ n $ segments.
So the problem reduces to:
> What is the maximum number of points $ x \in \{1, \dots, m\} $ for which we can observe $ f(x) $, such that there exists **at least one** consistent global assignment of segments (with some $ n' $) where **all** segments cover **some common point**?
That is, we want the largest possible $ |S| $ such that the observed $ f|_S $ is **compatible** with **some** covering where the intersection of all segments is **non-empty**.
---
### Key Insight:
Let $ g(x) $ be the number of segments covering $ x $ in some hypothetical scenario where **all segments contain a common point** $ c $. Then, the function $ g $ must be **unimodal** and **peaked at $ c $** — more precisely, if all segments contain $ c $, then the coverage function $ g $ must be **non-decreasing** to the left of $ c $ and **non-increasing** to the right of $ c $. Why?
Because any segment containing $ c $ must be an interval $ [l, r] $ with $ l \le c \le r $. So the number of segments covering $ x $ is the number of intervals such that $ l \le x \le r $. If all intervals contain $ c $, then:
- For $ x < c $: any segment covering $ x $ must have $ l \le x < c \le r $. So as $ x $ increases toward $ c $, more segments may start including $ x $ (if they start at $ x $), but none can drop out (since all contain $ c $), so $ g(x) $ is **non-decreasing** on $ [1, c] $.
- For $ x > c $: similarly, as $ x $ increases beyond $ c $, segments may drop out (if their right endpoint is $ < x $), but none can be added (since all contain $ c $, and $ l \le c \le r $, so for $ x > c $, only segments with $ r \ge x $ cover it), so $ g(x) $ is **non-increasing** on $ [c, m] $.
Thus, if **all segments contain a common point**, then the coverage function $ g $ is **bitonic**: non-decreasing to the left of some point $ c $, and non-increasing to the right.
Conversely, if the observed coverage function $ f $ on a set $ S $ is **not** consistent with any bitonic function (i.e., there is a "valley" or "local maximum not at the peak"), then we can be sure that **no common point exists**.
But we are to find the **maximum** size of a set $ S $ such that the observed $ f|_S $ **is consistent** with **some** bitonic function (i.e., Teodor might be lying).
So: We want the **largest subset** $ S \subseteq \{1, \dots, m\} $ such that the restriction $ f|_S $ can be extended to a bitonic function over $ \{1, \dots, m\} $.
But note: We are given the **true** coverage function $ f $ (from the input segments). We are to find the largest subset $ S \subseteq \{1, \dots, m\} $ such that **even though the true $ f $ has no point covered by all segments**, the values $ f(x) $ for $ x \in S $ **could** have come from a different set of segments (with possibly different $ n' $) that **do** have a common intersection.
So the problem becomes:
> Given the true coverage function $ f: \{1, \dots, m\} \to \mathbb{N} $, what is the size of the largest subset $ S \subseteq \{1, \dots, m\} $ such that there exists a **bitonic** function $ g: \{1, \dots, m\} \to \mathbb{N} $ with $ g(x) = f(x) $ for all $ x \in S $?
And we want the **maximum** such $ |S| $, over all possible bitonic $ g $ that agree with $ f $ on $ S $.
But note: We are not allowed to change $ f(x) $ — we are given $ f $, and we are to pick a subset $ S $ of points where we observe $ f(x) $, and we want that **there exists at least one** bitonic function $ g $ that matches $ f $ on $ S $, even though the true $ f $ is **not** bitonic (because no point is in all segments — so $ \max f(x) < n $, but more importantly, the true $ f $ is not necessarily bitonic).
Wait — actually, the true $ f $ is the coverage of the given segments. It is **not necessarily** bitonic. But the key is: **Sasha doesn't know the true segments** — he only sees $ f(x) $ on a subset $ S $. He wants to know: can I be sure that **no point is in all segments**?
He can be sure **only if** every possible extension of $ f|_S $ to a full coverage function over $ \{1, \dots, m\} $ **must** have $ \max f(x) < n' $, for any $ n' $ — but he doesn’t know $ n' $.
Actually, the correct interpretation is:
> Sasha cannot be sure Teodor is telling the truth if there exists **some** set of segments (with some $ n' $) that:
> - Produces the observed $ f(x) $ values on $ S $,
> - And **has a common point** in all segments.
So we are to find the **maximum** size of $ S \subseteq \{1, \dots, m\} $ such that there exists a **bitonic** function $ g $ (i.e., one that can be the coverage of segments sharing a common point) with $ g(x) = f(x) $ for all $ x \in S $.
Therefore, the answer is:
> The size of the **largest subset** $ S \subseteq \{1, \dots, m\} $ such that the restriction $ f|_S $ is **compatible** with **some** bitonic function $ g $ (i.e., there exists a bitonic $ g $ with $ g(x) = f(x) $ for all $ x \in S $).
This is equivalent to: What is the size of the **longest subsequence** of $ f(1), f(2), \dots, f(m) $ that is **bitonic**?
Wait — not subsequence, but **subset** of indices, not necessarily contiguous.
Actually, since the domain is ordered $ 1 < 2 < \dots < m $, and bitonic means: there exists a peak $ c $ such that $ g(1) \le g(2) \le \dots \le g(c) \ge g(c+1) \ge \dots \ge g(m) $.
We are to choose a subset $ S \subseteq \{1, \dots, m\} $, and we require that the values $ f(x) $ for $ x \in S $, when ordered by $ x $, form a bitonic sequence.
We want the **maximum** such $ |S| $.
This is the **longest bitonic subsequence** of the sequence $ f(1), f(2), \dots, f(m) $.
But note: we are allowed to **skip** points — we are choosing a subset $ S $, not necessarily contiguous.
So the problem reduces to:
> Compute the length of the **longest bitonic subsequence** of the array $ f[1..m] $, where $ f[i] $ is the number of segments covering point $ i $.
And this is the answer $ k $.
---
### Final Formal Statement:
Let $ f: \{1, 2, \dots, m\} \to \mathbb{N} $ be defined by $ f(x) = |\{ i \mid l_i \le x \le r_i \}| $.
Define a **bitonic sequence** as a sequence $ a_1 \le a_2 \le \dots \le a_k \ge a_{k+1} \ge \dots \ge a_n $ for some peak index $ k $.
We are to compute:
$$
\boxed{
\max \left\{ |S| : S \subseteq \{1, \dots, m\}, \text{ and } (f(x))_{x \in S \text{ in increasing order}} \text{ is bitonic} \right\}
}
$$
This is the **length of the longest bitonic subsequence** of the array $ [f(1), f(2), \dots, f(m)] $.
---
### Algorithm Note:
The longest bitonic subsequence can be computed in $ O(m \log m) $ time:
- Compute $ \text{LIS}[i] $: length of longest increasing subsequence ending at $ i $.
- Compute $ \text{LDS}[i] $: length of longest decreasing subsequence starting at $ i $.
- Then $ \text{bitonic}[i] = \text{LIS}[i] + \text{LDS}[i] - 1 $.
- Answer = $ \max_{1 \le i \le m} \text{bitonic}[i] $.
Thus, the answer is the length of the longest bitonic subsequence of the coverage array.
---
### Final Answer:
$$
\boxed{\text{length of the longest bitonic subsequence of } (f(1), f(2), \dots, f(m))}
$$