시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

あなたは Just Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである.ここでは略して JOI 社と呼ぶ.

JOI 社には社員が N 人いて,1 から N までの番号がついている.社員は全員時刻 0 から M まで働く.時 刻 0 および時刻 M には,社員全員が会社内にいなければならない.

今日は偶然にも,どの社員もちょうど 1 回ずつ外出する.社員 i (1 ≦ i ≦ N) は時刻 S i に会社を出て,時 刻 Ti に会社に戻る.2 人以上の社員が同じ時刻に会社に出入りすることはない.

JOI 社の入口には大きな扉が 1 つあり,社員はここからのみ会社に出入りすることができる.扉には錠 がついており,錠は開いているか閉まっているかのどちらかである.会社内からは自由に錠を開け閉めす ることができるが,会社の外からは合鍵を持った者のみが錠を開け閉めすることができる.時刻 0 には扉 の錠は閉まっている.

どの社員も,会社に戻る時点で,会社の中に入ることができなければならない.すなわち,すべての i (1 ≦ i ≦ N) に対し,社員 i が合鍵を持っているか,時刻 Ti に扉の錠が開いているかの,少なくともどちら かでなければならない.社員が会社に戻ったとき,および合鍵を持った社員が会社を出るとき,錠を閉め るかどうかは好きにしてよい.合鍵を持たない社員が会社を出るときは錠を閉めることはできない.

JOI 社の社長は,N 人の社員のうち K 人に合鍵を渡すことにした.合鍵の紛失を避けるため,社員同士 で合鍵の受け渡しを行うことはできない.また,JOI 社の社長は勤務時間の効率をとても重視するため,社 員は,自分自身が会社に出入りするときを除き,扉の錠を開け閉めすることはできない.

セキュリティ上の理由で,勤務時間 M のうち扉の錠が閉まっている時間の合計をできるだけ長くしたい.

社員の出入りの情報と,社員に渡す合鍵の個数が与えられる.勤務時間 M のうち,扉の錠の開け閉めを うまく管理したときの,扉の錠が閉まっている時間の合計の最大値を求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N, M, K が空白を区切りとして書かれている.これは,JOI 社の社員が N 人いて, 全員が時刻 0 から時刻 M まで働き,N 人のうち K 人に合鍵を渡すことを表す.
  • 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,整数 Si , Ti が空白を区切りとして書かれている.これは, 社員 i が時刻 Si に会社を出て,時刻 Ti に会社に戻ることを表す.

출력

標準出力に,勤務時間 M のうち,扉の錠の開け閉めをうまく管理したときの,扉の錠が閉まっている時 間の合計の最大値を表す整数を 1 行で出力せよ.

제한

  • 1 ≦ N ≦ 2 000.
  • 1 ≦ M ≦ 1 000 000 000.
  • 1 ≦ K < N.
  • 0 < Si < Ti < M (1 ≦ i ≦ N).
  • 任意の i, j (1 ≦ i ≦ N, 1 ≦ j ≦ N, i ≠ j) に対し,Si ≠ Sj , Si ≠ Tj , Ti ≠ Tj

예제 입력 1

4 20 2
3 11
5 15
6 10
12 18

예제 출력 1

13

この入出力例では,JOI 社には 4 人の社員がいて,そのうちの 2 人に合鍵を渡す.社員 2 と社員 4 に合 鍵を渡し,以下のようにすると,扉の錠が閉まっている時間の合計は 13 となる.

  • 時刻 0 に,扉の錠は閉まっている.
  • 時刻 3 に,社員 1 が会社を出る.社員 1 は合鍵を持っていないため,扉の錠は閉められない.
  • 時刻 5 に,社員 2 が会社を出て,扉の錠を閉める.
  • 時刻 6 に,社員 3 が会社を出る.社員 3 は合鍵を持っていないため,扉の錠は閉められない.
  • 時刻 10 に,社員 3 が会社に戻る.扉の錠は開けたままにしておく.
  • 時刻 11 に,社員 1 が会社に戻り,扉の錠を閉める.
  • 時刻 12 に,社員 4 が会社を出て,扉の錠を閉める.
  • 時刻 15 に,社員 2 が会社に戻り,扉の錠を閉める.
  • 時刻 18 に,社員 4 が会社に戻り,扉の錠を閉める.
  • 時刻 20 まで,扉の錠は閉まったままである.

扉の錠が閉まっている時間の合計が 13 を超えるような方法は存在しないため,13 を出力する.

예제 입력 2

20 100000 8
29930 89724
56133 70462
28063 78568
32483 64351
9410 20176
55809 62944
32450 85190
73536 73966
20452 78868
45458 63484
8286 47425
76018 81622
16736 49308
85383 94641
25100 40002
22158 22821
23508 41781
61709 98882
58110 78431
28448 89247

예제 출력 2

72454