/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は図書館で開催される読書マラソンに参加することにしました。図書館には 1 から N までの番号が付けられた N 冊の本が一列に並んでいます。
読書マラソンでは、 M 個の「読書プラン」が用意されています。各読書プラン i は、本棚の L_i 番目から R_i 番目までの本をまとめて読むというものです。
しかし、高橋君は時間が限られているため、最大 K 個の読書プランしか実行できません。
高橋君は、読んだ本の種類数（重複を除いた数）をできるだけ多くしたいと考えています。最大 K 個の読書プランを選んだとき、読むことができる本の種類数の最大値を求めてください。
ただし、同じ番号の本が複数の読書プランに含まれていても、種類数としては 1 種類としてカウントします。
制約
- 1 \leq N \leq 10^9
- 1 \leq M \leq 10^5
- 1 \leq K \leq \min(M, 10)
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
- 入力はすべて整数である
入力
N M K L_1 R_1 L_2 R_2 : L_M R_M
- 1 行目には、本の総数を表す N 、読書プランの個数を表す M 、選べる読書プランの最大個数を表す K が、スペース区切りで与えられる。
- 2 行目から M + 1 行目では、各読書プランの情報が与えられる。
- 1 + i 行目では、 i 番目の読書プランで読む本の番号の範囲の始点 L_i と終点 R_i が、スペース区切りで与えられる。
出力
最大 K 個の読書プランを選んだとき、読むことができる本の種類数の最大値を 1 行で出力せよ。
入力例 1
10 4 2 1 3 4 6 2 5 8 10
出力例 1
7
入力例 2
15 5 1 1 5 3 10 11 15 6 6 8 14
出力例 2
8
入力例 3
100 12 3 1 20 15 35 40 60 55 80 75 100 10 25 30 45 50 70 5 15 85 95 22 28 65 90
出力例 3
68
入力例 4
1000000000 30 10 1 10000000 5000000 20000000 25000000 50000000 40000000 70000000 80000000 120000000 110000000 150000000 160000000 210000000 200000000 260000000 270000000 330000000 320000000 390000000 400000000 450000000 440000000 500000000 510000000 570000000 560000000 630000000 640000000 700000000 690000000 760000000 770000000 830000000 820000000 880000000 890000000 930000000 920000000 970000000 960000000 1000000000 123456789 234567890 345678901 456789012 567890123 678901234 789012345 890123456 100000001 100000001 333333333 333333333 666666666 666666666 999999999 1000000000 1 1000000000
出力例 4
1000000000
入力例 5
1 1 1 1 1
出力例 5
1
Score : 466 pts
Problem Statement
Takahashi has decided to participate in a reading marathon held at the library. The library has N books lined up in a row, numbered from 1 to N.
For the reading marathon, M "reading plans" are prepared. Each reading plan i involves reading all the books from the L_i-th to the R_i-th book on the bookshelf.
However, since Takahashi has limited time, he can execute at most K reading plans.
Takahashi wants to maximize the number of distinct books he reads (counting without duplicates). When selecting at most K reading plans, find the maximum number of distinct books he can read.
Note that even if the same numbered book is included in multiple reading plans, it is counted as only 1 book in the total number of distinct books.
Constraints
- 1 \leq N \leq 10^9
- 1 \leq M \leq 10^5
- 1 \leq K \leq \min(M, 10)
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
- All inputs are integers
Input
N M K L_1 R_1 L_2 R_2 : L_M R_M
- The first line contains N representing the total number of books, M representing the number of reading plans, and K representing the maximum number of reading plans that can be selected, separated by spaces.
- From the 2nd line to the (M + 1)-th line, the information for each reading plan is given.
- The (1 + i)-th line contains the start L_i and end R_i of the range of book numbers to be read in the i-th reading plan, separated by spaces.
Output
Output in one line the maximum number of distinct books that can be read when selecting at most K reading plans.
Sample Input 1
10 4 2 1 3 4 6 2 5 8 10
Sample Output 1
7
Sample Input 2
15 5 1 1 5 3 10 11 15 6 6 8 14
Sample Output 2
8
Sample Input 3
100 12 3 1 20 15 35 40 60 55 80 75 100 10 25 30 45 50 70 5 15 85 95 22 28 65 90
Sample Output 3
68
Sample Input 4
1000000000 30 10 1 10000000 5000000 20000000 25000000 50000000 40000000 70000000 80000000 120000000 110000000 150000000 160000000 210000000 200000000 260000000 270000000 330000000 320000000 390000000 400000000 450000000 440000000 500000000 510000000 570000000 560000000 630000000 640000000 700000000 690000000 760000000 770000000 830000000 820000000 880000000 890000000 930000000 920000000 970000000 960000000 1000000000 123456789 234567890 345678901 456789012 567890123 678901234 789012345 890123456 100000001 100000001 333333333 333333333 666666666 666666666 999999999 1000000000 1 1000000000
Sample Output 4
1000000000
Sample Input 5
1 1 1 1 1
Sample Output 5
1