Problem : 336 - 廷廷的大秘寶

Problem Statistics

Solved Member: 16　　Submission: 49　　User Tried: 16

Statement:

方方是一名高級探員，日前他截獲一則知名犯罪集團「CRC」的消息，他們即將在大地主廷廷的一場宴會中偷走傳說中的大秘寶(ONE PIECE)! CRC要成功犯罪必須恰好同時有 k 個人聚集起來行動，且這 k 個人某個時刻都在宴會裡。

你知道宴會中每個人進場及出場的時間，你想要派你的探員們監視最少個賓客，使得任意一種犯罪的組合裡面都至少有一個人被監視。如此一來，當CRC想要犯罪時就可以讓探員回報給方方!

注意，兩個人同時在場中的情況只需要滿足在場內的時間有一瞬間相交即可。(在場時間 [1,2] 的賓客和在場時間 [2,3] 的賓客可以在時間點 2 合作犯罪。)

Input:Output:

第一行有兩個正整數 n, k，代表有 n 個人申請參加宴會以及「CRC」犯罪的人數 k。
接下來第 2 到第 n+1 行，每一行有兩個整數 $A_i, B_i$，代表第 i 個人進來宴會的時間為 $A_i$，離開時間為$B_i$。

$1 \le k \le n \le 100000$
$0 \le A_i \le B_i \le 10^9$

20% 的測試資料中滿足：$n \le 20$

輸出一個整數表示需要監視多少賓客。

Sample Input:Sample Output:

A:
3 2
1 3
3 5
4 6

B:
4 3
1 8
2 9
3 10
4 11

C:
4 3
1 5
4 9
8 13
12 17

A:
1

B:
2

C:
0

HINT:

第一筆範例：犯罪的所有可能為 {1,2} 或 {2,3}，監視第 2 個人就可以讓所有可能的組合都至少有一個人被監視。

第二筆範例：任意三個人都有可能是犯罪的組合，所以監視其中任意 2 人即可。

第三筆範例：不存在三個人同時在場的時間，所以沒有犯罪的可能。

Source:

103附中資奧選拔賽

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
0-3	1000ms	262144kb
1-1	1000ms	262144kb	20
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
1-5	1000ms	262144kb
1-6	1000ms	262144kb
2-1	1000ms	262144kb	20
2-2	1000ms	262144kb
2-3	1000ms	262144kb
2-4	1000ms	262144kb
2-5	1000ms	262144kb
2-6	1000ms	262144kb
3-1	1000ms	262144kb	20
3-2	1000ms	262144kb
3-3	1000ms	262144kb
3-4	1000ms	262144kb
3-5	1000ms	262144kb
3-6	1000ms	262144kb
4-1	1000ms	262144kb	20
4-2	1000ms	262144kb
4-3	1000ms	262144kb
4-4	1000ms	262144kb
4-5	1000ms	262144kb
4-6	1000ms	262144kb
5-1	1000ms	262144kb	20
5-2	1000ms	262144kb
5-3	1000ms	262144kb
5-4	1000ms	262144kb
5-5	1000ms	262144kb
5-6	1000ms	262144kb