C - Snow Depth Survey Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は気象観測所の職員です。東西に一直線に延びる道路上に、地点 1, 2, \ldots, N の N 個の観測地点がこの順に並んでおり、各地点の積雪状況を調査しています。

はじめ、すべての地点の積雪回数は 0 です。

この冬、合計 M 回の降雪がありました。i 回目 (1 \leq i \leq M) の降雪では、地点 L_i から地点 R_i までのすべての地点（両端を含む）において、それぞれ積雪回数が 1 だけ増加しました。

すなわち、M 回の降雪がすべて終わった後の各地点の積雪回数は、その地点が降雪の範囲に含まれた回数の合計に等しくなります。

上司の青木君から「積雪回数が K 以上の地点は除雪が必要だ」と連絡がありました。高橋君は除雪計画を立てるために、M 回の降雪がすべて終わった後に積雪回数が K 以上である地点の個数を求めたいです。

積雪回数が K 以上である地点の個数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq M
  • 1 \leq L_i \leq R_i \leq N
  • 入力はすべて整数である。

入力

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 行で出力せよ。

入力例 1

10 3 2
1 5
3 7
6 10

出力例 1

5

入力例 2

5 3 3
1 2
3 4
4 5

出力例 2

0

入力例 3

100 5 3
10 50
20 60
30 70
40 80
50 90

出力例 3

41

入力例 4

1000000 4 2
1 500000
250001 750000
500001 1000000
1 1000000

出力例 4

1000000

入力例 5

1 1 1
1 1

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is a staff member at a meteorological observatory. Along a road extending in a straight line from east to west, there are N observation points, numbered 1, 2, \ldots, N in order, and he is surveying the snow accumulation status at each point.

Initially, the snowfall count at every point is 0.

This winter, there were a total of M snowfalls. In the i-th snowfall (1 \leq i \leq M), the snowfall count increased by 1 at every point from point L_i to point R_i (inclusive).

In other words, after all M snowfalls have finished, the snowfall count at each point equals the total number of times that point was included in the range of a snowfall.

His supervisor Aoki informed him that "points with a snowfall count of K or more require snow removal." To create a snow removal plan, Takahashi wants to determine the number of points whose snowfall count is K or more after all M snowfalls have finished.

Find the number of points whose snowfall count is K or more.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq M
  • 1 \leq L_i \leq R_i \leq N
  • All input values 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 observation points N, the number of snowfalls M, and the threshold value K for requiring snow removal, separated by spaces.
  • The i-th line (1 \leq i \leq M) of the following M lines contains the left endpoint L_i and right endpoint R_i of the range of the i-th snowfall, separated by spaces.

Output

Output in one line the number of points whose snowfall count is K or more.

Sample Input 1

10 3 2
1 5
3 7
6 10

Sample Output 1

5

Sample Input 2

5 3 3
1 2
3 4
4 5

Sample Output 2

0

Sample Input 3

100 5 3
10 50
20 60
30 70
40 80
50 90

Sample Output 3

41

Sample Input 4

1000000 4 2
1 500000
250001 750000
500001 1000000
1 1000000

Sample Output 4

1000000

Sample Input 5

1 1 1
1 1

Sample Output 5

1