TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

75.7% (28/37)

Submission's AC Ratio

21.8% (56/257)

Description

有天你閒來沒事,所以你就去爬綿羊山(因為魯蛋沒開台)...

但是你突然發現爬綿羊山好累...所以你決定算一下爬綿羊山浪費體力的程度是多少=w=
綿羊山其實是一座山脈,山地跟平地的交界處剛好都在數線上的整數座標上,爬綿羊山浪費體力的程度為"連續山地的數量"

這時邪惡的小綿羊看到你在爬山,所以他決定派出N組軍隊,每組被分配到一個任務區間i, j,表示從座標 i 一路改造到座標 j ,軍隊會把i 到 j 之間的平地改造成山地、山地改造成平地。
每組軍隊改造完後都會有一個「爬綿羊山浪費體力的程度」。

現在你想知道所有「爬綿羊山浪費體力的程度」中的最大值。

Input Format

第一行有兩個正整數N, M,表示小綿羊派出的軍隊數及綿羊山的長度。
接下來N行依序為小綿羊派出的軍隊,每行有兩個正整數a, b,表示軍隊從a一路改造到b。

占總分30% N, M <= 1,000
占總分60% N <= 1,000 且 M < 231
占總分60% N, M <= 100,000
所有資料滿足 1 <= a,b <=M
且N < 100,000 ,M < 231

Output Format

輸出一個你認為是答案的東西

Sample Input

5 10
2 4
5 9
6 8
3 4
1 5

Sample Output

3

Hints

範例測資中,「爬綿羊山浪費體力的程度」最大的情況有兩種:
平高平平高平平高平平 -> 三段
高平高高平平平高平平 -> 三段

一開始綿羊山是一塊平地,而且軍隊不一定會往前,也有可能往後走。

Problem Source

Subtasks

For Testdata: 0 ~ 9, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144