/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は N 枚の板からなるフェンスを塗装する仕事を請け負いました。板には 1 から N までの番号が付いており、最初すべての板は未塗装です。
青木君は高橋君に M 回の塗装指示を出します。i 回目 (1 \leq i \leq M) の指示は「板 L_i から板 R_i まで（両端を含む）のすべての板を塗る」というものです。ある板が複数の指示によって塗られる場合も、その板は 1 回塗装されたのと同じ状態になります。
高橋君は体力の都合上、M 回の指示のうち連続するちょうど K 回分の指示を無視しなければなりません。具体的には、1 \leq s \leq M - K + 1 を満たす整数 s を 1 つ選び、s 回目から s + K - 1 回目までの K 回の指示を無視して実行せず、それ以外の M - K 回の指示をすべて実行します。
高橋君は、無視する区間を最適に選ぶことで、最終的に塗装されている板の枚数を最大化したいです。最終的に塗装されている板の枚数の最大値を求めてください。
制約
- 1 \leq N \leq 10^9
- 1 \leq M \leq 2 \times 10^5
- 1 \leq K \leq M
- 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 \vdots L_M R_M
1 行目には、板の枚数 N、指示の回数 M、無視する連続した指示の回数 K がスペース区切りで与えられる。続く M 行のうち i 行目 (1 \leq i \leq M) には、i 回目の指示で塗る範囲の左端 L_i と右端 R_i がスペース区切りで与えられる。
出力
無視する連続した K 回の指示を最適に選んだとき、最終的に塗装されている板の枚数の最大値を整数で出力せよ。
入力例 1
10 4 2 1 3 4 6 2 5 8 10
出力例 1
7
入力例 2
8 5 1 1 4 3 6 5 8 2 2 7 7
出力例 2
8
入力例 3
50 10 3 1 10 5 15 20 25 12 22 30 40 35 45 2 8 18 19 41 50 10 30
出力例 3
50
入力例 4
1000000000 25 7 1 100000 50000 200000 150000 300000 250000 400000 350000 500000 450000 600000 550000 700000 650000 800000 750000 900000 850000 1000000 10000000 20000000 15000000 25000000 24000000 30000000 100000000 200000000 180000000 260000000 250000000 350000000 340000000 420000000 500000000 600000000 590000000 700000000 690000000 800000000 799999999 900000000 850000000 950000000 940000000 1000000000 123456789 123456789 400000000 500000000
出力例 4
920350003
入力例 5
1 1 1 1 1
出力例 5
0
Score : 433 pts
Problem Statement
Takahashi has been hired to paint a fence consisting of N boards. The boards are numbered from 1 to N, and initially all boards are unpainted.
Aoki gives Takahashi M painting instructions. The i-th instruction (1 \leq i \leq M) is "paint all boards from board L_i to board R_i (inclusive)." If a board is painted by multiple instructions, it ends up in the same state as if it were painted once.
Due to his limited stamina, Takahashi must ignore exactly K consecutive instructions out of the M instructions. Specifically, he chooses an integer s satisfying 1 \leq s \leq M - K + 1, ignores the K instructions from the s-th to the (s + K - 1)-th (not executing them), and executes all the remaining M - K instructions.
Takahashi wants to maximize the number of boards that are ultimately painted by optimally choosing the interval of instructions to ignore. Find the maximum number of boards that are ultimately painted.
Constraints
- 1 \leq N \leq 10^9
- 1 \leq M \leq 2 \times 10^5
- 1 \leq K \leq M
- 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 \vdots L_M R_M
The first line contains the number of boards N, the number of instructions M, and the number of consecutive instructions to ignore K, separated by spaces. The i-th (1 \leq i \leq M) of the following M lines contains the left endpoint L_i and right endpoint R_i of the range to paint in the i-th instruction, separated by spaces.
Output
Output the maximum number of boards that are ultimately painted as an integer, when the consecutive K instructions to ignore are chosen optimally.
Sample Input 1
10 4 2 1 3 4 6 2 5 8 10
Sample Output 1
7
Sample Input 2
8 5 1 1 4 3 6 5 8 2 2 7 7
Sample Output 2
8
Sample Input 3
50 10 3 1 10 5 15 20 25 12 22 30 40 35 45 2 8 18 19 41 50 10 30
Sample Output 3
50
Sample Input 4
1000000000 25 7 1 100000 50000 200000 150000 300000 250000 400000 350000 500000 450000 600000 550000 700000 650000 800000 750000 900000 850000 1000000 10000000 20000000 15000000 25000000 24000000 30000000 100000000 200000000 180000000 260000000 250000000 350000000 340000000 420000000 500000000 600000000 590000000 700000000 690000000 800000000 799999999 900000000 850000000 950000000 940000000 1000000000 123456789 123456789 400000000 500000000
Sample Output 4
920350003
Sample Input 5
1 1 1 1 1
Sample Output 5
0