17721번 - Keys 서브태스크다국어

あなたは 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 が合鍵を持っているか，時刻 T_i に扉の錠が開いているかの，少なくともどちら かでなければならない．社員が会社に戻ったとき，および合鍵を持った社員が会社を出るとき，錠を閉め るかどうかは好きにしてよい．合鍵を持たない社員が会社を出るときは錠を閉めることはできない．

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

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

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

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

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

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

• 1 ≦ N ≦ 2 000．
• 1 ≦ M ≦ 1 000 000 000．
• 1 ≦ K < N．
• 0 < S_i < T_i < M (1 ≦ i ≦ N)．
• 任意の i, j (1 ≦ i ≦ N, 1 ≦ j ≦ N, i ≠ j) に対し，S_i ≠ S_j , S_i ≠ T_j , T_i ≠ T_j．

• N ≦ 20 を満たす．
• M ≦ 1 000 000 を満たす．

追加の制限はない．