TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

76.5% (39/51)

Submission's AC Ratio

26.1% (77/295)

Tags

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 1

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

Sample Output 1

3

Hints

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

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

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1