問題

背景

うなぎ王国の学生たちはいつも学校の地下にある学生室で勉強している．学生室にはいつも学生がいるため普段はきれいに掃除されているが，夏休みになると学生が学校に来なくなるため，学生室は埃だらけになってしまう．そこで学生たちは夏休みの間も学校にやってきて学生室の掃除をすることにした．しかし学生たちは学校に来られる日が限られており，かつあまり学校に来たがらない．とりあえず各学生には一度ずつ掃除を頼むことにしたが，それでは十分ではないので何人かには毎日学校に来てもらおう．どういう割り当てにすれば学生室をきれいに保てるだろうか．

課題

最も長く掃除が行われない期間が最小になるように掃除の担当を割り当てたときに，その期間が何日になるかを答えよ．

学生の人数 N，夏休みの日数 M，パラメータ K が与えられる． i 番目の学生は a_i から b_i の間の日にしか学校に来ることはできない．また各学生に対して一度しか掃除を頼むことはできない．ただし K 人の学生を好きなように選んで，その学生には学校に来ることのできる期間に毎日学校に来てもらうように頼むことができる．

配点

200

入力

入力は以下の形式で与えられる．

N M K
a1 b1
...
aN bN

N は学生の数，M は夏休みの日数，K は毎日学校に来る学生の数，a_i，b_i は i 番目の学生が学校に来ることのできる期間を表す．

制約

入力中の各変数は以下の制約を満たす．

• 1 \leq N \leq 10⁵
• 1 \leq M \leq 10⁹
• 0 \leq K \leq N
• 1 \leq a_i \leq b_i \leq M

部分点

この問題には部分点が設定されている．この問題のテストケースのうち50点分は，追加で以下の制約も満たす．

• K=0

出力

問題の解を1行に出力せよ．

入力例1

1 2 0
1 2

入力例1に対する出力例

2

1日目に当番になっても2日目に当番になっても最長の間隔は2日になる．

入力例2

1 2 1
1 2

入力例2に対する出力例

1

毎日学校に来ることができるので，最長の間隔は1日になる．

入力例3

2 6 1
2 2
4 5

入力例3に対する出力例

2