Problem : 252 - Teleporters

Problem Statistics

Solved Member: 11　　Submission: 55　　User Tried: 11

Statement:

你正在參加一項沿著直線路線自西向東橫穿埃及的比賽。開始時你位於這條直線路線的最西端。根據比賽規則，你必須要沿著這條直線路線始終向東行進。

在這條直線路線上有N 個傳送器。每個傳送器都有兩個端點。每當你到達某個傳送器的兩個端點之一時，傳送器都會立即將你傳送到該傳送器的另一個端點（注意，根據你所在的端點位置，傳送器能夠將你從當前位置向東或者向西傳送）。當你被傳送到另一個端點之後，你必須繼續沿這條直線路線向東行進；你無法避開你前進路上的任何傳送器端點。絕不會出現兩個端點在同一位置的情形。所有端點都嚴格位於這條直線路線的起點和終點之間。

每當你被傳送一次，你就會獲得1分。比賽的目標就是獲取盡可能多的分數。為使獲得的分數最多，允許你在比賽開始前在這條路線上增設M 個新的傳送器。使用這些新的傳送器你也同樣可以獲得分數。

你可以將這些新傳送器的端點設在任何位置上（甚至是非整數坐標點也可以），只要這些坐標點並不出現在已經被另一個端點佔用的位置上即可。換句話說，所有傳送器的端點位置必須是唯一的。同樣，新傳送器的端點都必須嚴格位於這條直線路線的起點和終點之間。

題目可以保證，不管你如何增設這些傳送器，你一定可以到達比賽路線的終點。

Task:

編寫一個程序，對於給定的N 個傳送器的端點位置和你可以增設的新傳送器的數目M ，計算你能獲得的最高分數。

Input:Output:

你的程序必須從標準輸入中讀入下列數據：

• 第1行包含一個整數N ，表示開始時在路線上的傳送器數目

• 第2行包含一個整數M，表示你可以增設的新傳送器的最大數目

• 隨後的N 行每行描述一個傳送器。第i行描述第i個傳送器。每行有兩個整數Wi 和Ei，以一個空格分隔。這兩個整數分別描述從路線起點到該傳送器的兩個端點的距離。

對於給定的這些傳送器，沒有任何兩個端點在同一位置上。比賽路線的起點為位置0，而終點則在位置2,000,001上。

你的程式必須輸出一個整數至標準輸出，即最高可得分數。

Sample Input:Sample Output:

Sample #1:
3
1
10 11
1 4
2 3

Sample #2:
3
3
5 7
6 10
1999999 2000000

Sample #1:
6

Sample #2:
12

HINT:

限制條件1 <= N <= 1,000,000

開始時在路線上的傳送器的數目1 <= M <= 1,000,000

你可以增設的新傳送器的最大數目1 <= W_X < E_X <= 2,000,000 分別為從路線的起點到傳送器X 的西端點和東端點的距離

Source:

IOI 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	1000ms	65536kb	2
2	1000ms	65536kb	2
3	1000ms	65536kb	2
4	1000ms	65536kb	3
5	1000ms	65536kb	3
6	1000ms	65536kb	3
7	1000ms	65536kb	3
8	1000ms	65536kb	3
9	1000ms	65536kb	3
10	1000ms	65536kb	3
11	1000ms	65536kb	3
12-1	1000ms	65536kb	7
12-2	1000ms	65536kb
13-1	1000ms	65536kb	7
13-2	1000ms	65536kb
13-3	1000ms	65536kb
14	1000ms	65536kb	8
15	1000ms	65536kb	8
16-1	1000ms	65536kb	8
16-2	1000ms	65536kb
17-1	1000ms	65536kb	8
17-2	1000ms	65536kb
18-1	2000ms	65536kb	8
18-2	2000ms	65536kb
18-3	2000ms	65536kb
19-1	2000ms	65536kb	8
19-2	2000ms	65536kb
19-3	2000ms	65536kb
19-4	2000ms	65536kb
20-1	2000ms	65536kb	8
20-2	2000ms	65536kb
20-3	2000ms	65536kb
20-4	2000ms	65536kb