{"problem":{"name":"F. Teodor is not a liar!","description":{"content":"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 featu","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF931F"},"statements":[{"statement_type":"Markdown","content":"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.\n\nSasha 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.\n\nBoth 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.\n\n## Input\n\nFirst 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.\n\n_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.\n\nIt is guaranteed that there is no integer point, that belongs to all segments.\n\n## Output\n\nSingle 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_).\n\n[samples]\n\n## Note\n\nFirst 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.\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"年轻的Teodor喜欢绘画。他最喜爱的爱好是在他巨大的#cf_span[[1;m]]线段内绘制端点为整数的线段。一天，Teodor注意到他刚刚画出的图案具有一种有趣的特性：不存在一个整数点，属于图案中的每一条线段。发现这一事实后，Teodor决定与Sasha分享。\n\nSasha知道Teodor喜欢炫耀，因此从不信任他。Teodor想证明自己有时是可信的，于是决定说服Sasha：他的图案中确实不存在属于所有线段的整数点。然而，Teodor是个懒人，既不想告诉Sasha所有线段端点的坐标，也不想告诉他线段的数量，于是他建议Sasha向他提出一系列问题：“给定一个整数点#cf_span[xi]，Teodor的图案中有多少条线段包含这个点？”，并承诺会给出这些问题的正确答案。\n\n两个男孩都忙于学习，没有太多时间，因此你需要找出：Sasha可以向Teodor提问的最大问题数k，使得仅根据这些回答，Sasha仍无法确定Teodor是否在撒谎。注意，Sasha并不知道Teodor图案中线段的总数。当然，Sasha是个聪明人，绝不会对同一个点重复提问。\n\n输入的第一行包含两个整数：#cf_span[n]和#cf_span[m]（#cf_span[1 ≤ n, m ≤ 100 000]）——分别表示Teodor图案中的线段数量和Sasha可以询问的最大坐标。\n\n接下来的#cf_span[n]行中，第#cf_span[i]行包含两个整数#cf_span[li]和#cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ m]）——表示第#cf_span[i]条线段的左端点和右端点。注意，线段的左右端点可以是同一个点。\n\n保证不存在一个整数点，属于所有线段。\n\n输出仅一行，包含一个整数#cf_span[k]——表示最大的集合#cf_span[(xi, cnt(xi))]的大小，其中所有#cf_span[xi]互不相同，#cf_span[1 ≤ xi ≤ m]，且#cf_span[cnt(xi)]表示包含坐标为#cf_span[xi]的点的线段数量，使得仅知道这个集合（而不知道#cf_span[n]）时，仍无法确定原始图案中不存在属于所有线段的点。\n\n## Input\n\n第一行输入包含两个整数：#cf_span[n]和#cf_span[m]（#cf_span[1 ≤ n, m ≤ 100 000]）——分别表示Teodor图案中的线段数量和Sasha可以询问的最大坐标。第#cf_span[i]行接下来的#cf_span[n]行包含两个整数#cf_span[li]和#cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ m]）——表示第#cf_span[i]条线段的左端点和右端点。注意，线段的左右端点可以是同一个点。保证不存在一个整数点，属于所有线段。\n\n## Output\n\n输出仅一行，包含一个整数#cf_span[k]——表示最大的集合#cf_span[(xi, cnt(xi))]的大小，其中所有#cf_span[xi]互不相同，#cf_span[1 ≤ xi ≤ m]，且#cf_span[cnt(xi)]表示包含坐标为#cf_span[xi]的点的线段数量，使得仅知道这个集合（而不知道#cf_span[n]）时，仍无法确定原始图案中不存在属于所有线段的点。\n\n[samples]\n\n## Note\n\n第一个例子展示了Sasha永远无法确定Teodor是否在撒谎的情况：即使他知道线段#cf_span[[1;4]]中每个点的#cf_span[cnt(xi)]，也无法区分这种情况与Teodor仅画了一条完整的#cf_span[[1;4]]线段的情况。\n\n在第二个例子中，Sasha可以询问5个点，例如#cf_span[1, 2, 3, 5, 6]，但仍无法确定Teodor是否在撒谎。但一旦他知道了#cf_span[[1;6]]中所有点的信息，就能确定Teodor没有撒谎。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ f(x) $ denote the number of segments containing integer point $ x \\in [1, m] $.\n\nGiven:  \n- There are $ n $ segments $ [l_i, r_i] \\subseteq [1, m] $, with $ 1 \\leq l_i \\leq r_i \\leq m $.  \n- **No integer point belongs to all $ n $ segments**, i.e., $ \\bigcap_{i=1}^n [l_i, r_i] = \\emptyset $.  \n- Sasha learns $ f(x) $ for some subset of points $ x \\in [1, m] $, without knowing $ n $ or the segments.  \n- Sasha wants to determine whether **there exists** a point contained in **all** segments (i.e., whether Teodor is lying).  \n- Teodor claims **no** such point exists.  \n- Sasha **cannot be sure** Teodor is telling the truth if **there exists** some alternative set of segments (with possibly different $ n' $) that produces the **same** $ f(x) $ values on the queried points, but **does have** a common intersection point.\n\nWe are to find the **maximum size** of a set $ S = \\{ (x_i, f(x_i)) \\} $, with all $ x_i $ distinct in $ [1, m] $, such that **it is still possible** that some point lies in all segments — i.e., Sasha **cannot rule out** that Teodor is lying.\n\n---\n\n### Key Insight:\n\nThe function $ f(x) $ is the **coverage count** at point $ x $. It is a piecewise constant function that changes only at segment endpoints.\n\nThe condition that **no point belongs to all segments** means:  \n$$\n\\min_{x \\in [1,m]} f(x) < n\n$$\n\nBut Sasha **does not know $ n $**. So he only sees the values $ f(x) $ at queried points.\n\nSasha **cannot be sure** Teodor is telling the truth if there exists **some** integer $ n' \\geq 1 $ and some collection of $ n' $ segments such that:\n1. The coverage function $ f'(x) $ matches $ f(x) $ on all queried points $ x_i $,  \n2. And $ \\min_{x \\in [1,m]} f'(x) = n' $ — meaning **every** queried point has coverage $ \\leq n' $, but **some unqueried point** has coverage $ n' $, and **all segments contain that point**.\n\nIn other words:  \nSasha **cannot distinguish** the true configuration from a **fake** one where **all segments share a common point**, and the coverage function matches on the queried points.\n\nSo we want the **largest** set of points $ \\{x_1, \\dots, x_k\\} $ with known $ f(x_i) $, such that **there exists** a possible global coverage function $ f' $ (induced by some set of segments) where:\n- $ f'(x_i) = f(x_i) $ for all queried $ x_i $,  \n- and $ \\min_{x \\in [1,m]} f'(x) = \\max_{x \\in [1,m]} f'(x) = n' $ — i.e., **all** points have the same coverage $ n' $, meaning **every point is in all $ n' $ segments**.\n\nWait — that would mean the entire interval is covered by $ n' $ identical segments. But that’s not necessary.\n\nActually, the **minimal** coverage over all points must equal the **maximum** coverage for there to be a common intersection. Because:\n\n> A set of intervals has a common intersection **iff** the point with the **minimum** coverage is covered by **all** intervals — i.e., $ \\min_x f(x) = n $.\n\nSo if Sasha sees a set of values $ f(x_i) $, and **for every possible extension** of $ f $ to the entire $ [1,m] $, it is possible that $ \\min_x f(x) = \\max_x f(x) $, then he cannot be sure.\n\nBut we want the **maximum** size of a set of points $ \\{x_i\\} $ such that **there exists** a valid extension where $ \\min f(x) = \\max f(x) $ — i.e., **all** points have the same coverage.\n\nThat is:  \n> What is the largest set of points $ S \\subseteq [1,m] $, with values $ f(x_i) $, such that **there exists** a constant function $ f'(x) = c $ for all $ x \\in [1,m] $, and $ f'(x_i) = f(x_i) $ for all $ x_i \\in S $?\n\nBut $ f'(x) = c $ for all $ x $ means that **every integer point in $ [1,m] $** is covered by exactly $ c $ segments — which is only possible if all segments are the **full interval** $ [1,m] $, and there are $ c $ of them.\n\nSo:  \nThe only way to have $ f'(x) = c $ for all $ x \\in [1,m] $ is if **all segments are $ [1,m] $**.\n\nThus, the only constant coverage function possible is $ f(x) = c $ for all $ x \\in [1,m] $, achieved by $ c $ copies of $ [1,m] $.\n\nTherefore, Sasha **cannot be sure** Teodor is telling the truth **if and only if** the values $ f(x_i) $ he has seen are **all equal** to some constant $ c $, and **it is possible** that all segments are $ [1,m] $, i.e., $ f(x) = c $ everywhere.\n\nSo:  \n- If **all queried points** have the same coverage value $ c $, then Sasha **cannot rule out** that Teodor has drawn $ c $ copies of $ [1,m] $ — in which case **every point** is in all segments — meaning Teodor is lying.\n\n- But if **any two queried points** have **different** coverage values, then it is **impossible** that all segments share a common point — because if they did, all points would have the same coverage $ n $.\n\nTherefore:\n\n> Sasha **can be sure** Teodor is telling the truth **iff** there exist **two queried points** $ x_1, x_2 $ with $ f(x_1) \\ne f(x_2) $.\n\n> Sasha **cannot be sure** if **all queried points** have the same coverage value.\n\nSo the **largest** set of points $ S $ such that Sasha **cannot be sure** is the **largest** subset of $ [1,m] $ where **all points have the same coverage**.\n\nThus, the answer is:\n\n$$\n\\boxed{ \\max_{c} \\left| \\left\\{ x \\in [1, m] : f(x) = c \\right\\} \\right| }\n$$\n\nThat is, the **maximum number of integer points in $ [1, m] $** that have the **same** coverage count.\n\n---\n\n### Algorithm:\n\n1. Compute $ f(x) $ for all $ x \\in [1, m] $ using a difference array (or sweep line).\n2. Count frequency of each coverage value $ c $.\n3. Return the maximum frequency.\n\n---\n\n### Example:\n\n**Input:**  \nn=2, m=4  \nSegments: [1,2], [3,4]\n\nThen:  \nf(1)=1, f(2)=1, f(3)=1, f(4)=1 → all coverage = 1 → max frequency = 4 → output 4.\n\n**Another:**  \nn=3, m=6  \nSegments: [1,3], [2,4], [5,6]  \nf(1)=1, f(2)=2, f(3)=2, f(4)=1, f(5)=1, f(6)=1  \nCoverage counts:  \n1: x=1,4,5,6 → count=4  \n2: x=2,3 → count=2  \nMax = 4 → output 4.\n\nBut wait — the problem says in the **second example**, Sasha can ask 5 points and still not be sure, but not all 6.\n\nSo let’s check the second example.\n\nThe problem says:  \n> 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.\n\nSo if the true coverage is:  \nx: 1 2 3 4 5 6  \nf: 1 2 2 1 1 1\n\nSasha queries 5 points: say 1,2,3,5,6 → values: 1,2,2,1,1 → he sees values 1 and 2 → so he **can** be sure? But the problem says he **cannot** be sure.\n\nContradiction?\n\nWait — re-read:  \n> Sasha can ask about 5 points e.g. 1,2,3,5,6, still not being sure...\n\nBut he sees f(1)=1, f(2)=2, f(3)=2, f(5)=1, f(6)=1 — so he sees both 1 and 2.\n\nWhy can't he be sure?\n\nBecause he doesn’t know n. He sees max coverage = 2, min = 1.\n\nHe thinks: maybe there are 2 segments, and they are both [2,3] — then f(2)=f(3)=2, others=0 — but he sees f(1)=1, so that’s impossible.\n\nWait — maybe he considers: what if the true set of segments is **not** the given one, but a different one that produces the same coverage on queried points, but has a common intersection?\n\nCan he construct a set of segments with **common intersection**, that matches the coverage on {1,2,3,5,6}?\n\nSuppose he assumes there is a point common to all segments — say point 4.\n\nHe sees f(1)=1, f(2)=2, f(3)=2, f(5)=1, f(6)=1.\n\nCan he find segments such that:\n- All segments contain point 4? → so all segments must cover 4.\n- Coverage at 1:1, 2:2, 3:2, 5:1, 6:1.\n\nSuppose there are 2 segments:  \nSegment A: [2,5] → covers 2,3,4,5  \nSegment B: [1,3] → covers 1,2,3\n\nThen coverage:  \n1:1, 2:2, 3:2, 4:1, 5:1, 6:0 → but f(6)=1 is observed → contradiction.\n\nAnother try: 3 segments.\n\nSuppose all segments contain 4.\n\nLet’s try:\n- [1,4] → covers 1,2,3,4  \n- [2,5] → covers 2,3,4,5  \n- [4,6] → covers 4,5,6\n\nThen coverage:  \n1:1, 2:2, 3:2, 4:3, 5:2, 6:1\n\nBut we need f(5)=1, f(6)=1 — here f(5)=2 — too high.\n\nTry:\n- [1,3]  \n- [3,5]  \n- [5,6]  \nBut then 4 is only covered by [3,5] — so if we require **all segments contain 4**, then [1,3] cannot exist.\n\nSo to have all segments contain 4, every segment must satisfy $ l_i \\leq 4 \\leq r_i $.\n\nSo possible segments:  \nWe need to cover:  \nx=1: count=1 → only one segment covers 1 → so one segment must start at 1 and extend to ≥4  \nx=2: count=2 → two segments cover 2 → so two segments must have l_i ≤2  \nx=3: count=2 → two segments cover 3  \nx=5: count=1 → one segment covers 5 → so one segment must end at 5 or later, but only one  \nx=6: count=1 → one segment ends at 6\n\nSo let’s try:\n\nSegment 1: [1,6] → covers 1,2,3,4,5,6  \nSegment 2: [2,5] → covers 2,3,4,5  \nSegment 3: [4,6] → covers 4,5,6\n\nCoverage:  \n1:1, 2:2, 3:2, 4:3, 5:3, 6:2 → doesn’t match.\n\nWe need f(5)=1, f(6)=1 — so only one segment covers 5 and 6.\n\nSo only one segment can extend to 6. But if all segments contain 4, then that segment must be [a,6] with a≤4.\n\nTo have f(5)=1, only one segment can cover 5 → so only one segment has r_i ≥5.\n\nSimilarly, f(6)=1 → only one segment has r_i ≥6 → so only one segment ends at 6 or beyond.\n\nSo the only segment that can cover 5 or 6 is one segment: say [a,6], a≤4.\n\nThen f(5)=1, f(6)=1 → good.\n\nNow f(1)=1 → only one segment covers 1 → so only one segment has l_i ≤1 → so one segment must be [1,6].\n\nThen f(2)=2 → two segments cover 2 → one is [1,6], so need one more segment covering 2 → say [2,4]  \nf(3)=2 → [1,6] and [2,4] cover 3 → good  \nf(4)=? → [1,6] and [2,4] → so f(4)=2\n\nBut we didn’t query 4! So we don’t care what f(4) is.\n\nSo the coverage we have:  \nx: 1 2 3 5 6  \nf: 1 2 2 1 1\n\nSegments:  \n- [1,6]  \n- [2,4]\n\nAll segments contain 4?  \n[1,6] → yes  \n[2,4] → yes → so common point 4 exists!\n\nAnd coverage on queried points matches.\n\nSo even though the true configuration has no common point, **there exists another configuration** with common point 4 that matches the observed coverage on {1,2,3,5,6}.\n\nThus, Sasha **cannot be sure**.\n\nBut if he queries **all 6 points**, then he sees f(4)=2, and the maximum coverage is 2, but min is 1 → so min < max → so **no point** can be in all segments → because if all segments contained some point x, then f(x) = n, and for any other point y, f(y) ≤ n, but if f(y) < n, then y is not in all segments → contradiction unless f(y)=n everywhere.\n\nBut here f(1)=1, f(2)=2 → so if n=2, then f(1)=1 < 2 → so point 1 is not in all segments → so no common point.\n\nSo if **all** points are queried, and min f(x) < max f(x), then Sasha knows: **no point is in all segments**.\n\nSo the condition for **Sasha being unsure** is:  \nThere exists **some** constant c, and **some** assignment of segments such that:\n- All segments contain a common point (say x0),\n- The coverage function f’ on the queried points matches the true f on those points,\n- And f’(x0) = n' = max coverage.\n\nAnd this is possible **iff** the queried points do **not** include any point with coverage strictly less than the maximum coverage seen.\n\nIn other words:  \nSasha is unsure if the **set of queried points** does **not** include a point with **minimum** coverage.\n\nWait — no.\n\nActually, from above:  \nSasha is unsure if **there exists** a configuration with a common intersection that matches the observed coverage on queried points.\n\nThat configuration requires that **all segments contain some point x0**, so **every queried point** must be covered by **at most** n' segments, and **x0** must be covered by n' segments.\n\nBut if **all queried points** have coverage **equal to the maximum** observed value, then it’s possible that x0 is unqueried, and all segments contain x0, and the coverage at queried points is less than or equal to n', but we only see the max.\n\nWait — no.\n\nLet’s define:\n\nLet M = max{ f(x_i) | queried x_i }\n\nIf **all** queried points have f(x_i) = M, then it is possible that the true coverage everywhere is M (all segments are [1,m]), or that the coverage is M at queried points, and higher at unqueried points — but that’s impossible because coverage can’t be higher than n, and if a point has coverage > M, then M is not the max.\n\nActually, coverage is determined by the segments — so if a point x0 has coverage c, and all queried points have coverage ≤ c, then if c = M, and x0 is unqueried, then it’s possible that x0 has coverage M, and all segments contain x0.\n\nBut if **some** queried point has coverage < M, then since all segments containing x0 must cover that point, then f(x) ≥ n for all x — contradiction, because we have f(x) < M = n.\n\nSo:\n\n> Sasha **can be sure** Teodor is truthful **iff** there exists a queried point x with f(x) < M, where M = max{ f(x_i) }.\n\n> Sasha **cannot be sure** if **all** queried points have f(x_i) = M.\n\nTherefore, the largest set of points where Sasha **cannot be sure** is the largest subset of [1,m] where **all points have the same coverage value**, and that value is the **global maximum** coverage.\n\nWait — not necessarily the global maximum.\n\nActually, the condition is:  \nSasha is unsure if **there exists** a value c such that **all queried points have coverage c**, and **c is achievable as the coverage of a common intersection point** in some configuration.\n\nBut if all queried points have coverage c, then Sasha can assume:  \n- There are c segments, all equal to [1,m] → then every point has coverage c → so common intersection exists → Teodor is lying.\n\nSo **any** set of points where all have the same coverage c allows this fake explanation.\n\nSo the **maximum** size of such a set is the **maximum number of points** that have the **same coverage value**, regardless of what that value is.\n\nBecause if k points all have coverage c, then Sasha cannot rule out that the true picture is c copies of [1,m], which would have coverage c everywhere — so common intersection exists.\n\nTherefore, the answer is:\n\n> The **maximum frequency** of any coverage value over all points in [1,m].\n\n---\n\n### Final Answer:\n\nCompute the coverage function $ f(x) $ for $ x = 1 $ to $ m $ using a difference array.\n\nCount frequency of each coverage value.\n\nOutput the **maximum frequency**.\n\n```python\nn, m = map(int, input().split())\ndiff = [0] * (m + 2)\n\nfor _ in range(n):\n    l, r = map(int, input().split())\n    diff[l] += 1\n    diff[r + 1] -= 1\n\nf = [0] * (m + 1)\ncur = 0\nfor i in range(1, m + 1):\n    cur += diff[i]\n    f[i] = cur\n\nfrom collections import Counter\nfreq = Counter(f[1:])\nprint(max(freq.values()))\n```","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF931F","tags":["data structures","dp"],"sample_group":[["2 4\n1 2\n3 4","4"],["4 6\n1 3\n2 3\n4 6\n5 6","5"]],"created_at":"2026-03-03 11:00:39"}}