AT_abc463_d [ABC463D] Maximize the Gap

数直線上に $ N $ 枚の布があります。 $ i $ 枚目 $ (1\le i\le N) $ の布は数直線上の区間 $ \lbrack L _ i,R _ i\rbrack $ を覆っています。 数直線上の点は $ 2 $ 枚以上の布で覆われていることも、どの布にも覆われていないこともあります。 $ 2 $ 枚の布が重なっているとは、数直線上のある点がその $ 2 $ 枚の布どちらにも覆われていることをいいます。 重なっていない $ 2 $ 枚の布について、それらの**距離**を以下のように定めます。 - 一方の布に覆われている点 $ p $ ともう一方の布に覆われている点 $ q $ に対する $ |p-q| $ の最小値 どの $ 2 $ 枚も重なっていない $ K $ 枚の布に対して、その**スコア**を布どうしの距離の最小値と定めます。 $ N $ 枚の布からどの $ 2 $ 枚も重なっていないように $ K $ 枚を選ぶときのスコアの最大値を求めてください。 ただし、そのように $ K $ 枚の布を選ぶことができない場合、`-1` を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ L _ 1 $ $ R _ 1 $ $ L _ 2 $ $ R _ 2 $ $ \vdots $ $ L _ N $ $ R _ N $

答えを出力せよ。

### Sample Explanation 1 $ 2 $ 枚目、 $ 4 $ 枚目、 $ 6 $ 枚目の布を選ぶと、これらはどの $ 2 $ 枚も重なっていません。 $ 2 $ 枚目の布と $ 4 $ 枚目の布の距離は $ 2 $ 、 $ 2 $ 枚目の布と $ 6 $ 枚目の布の距離は $ 8 $ 、 $ 4 $ 枚目の布と $ 6 $ 枚目の布の距離は $ 2 $ なので、この選び方のスコアは $ 2 $ です。 スコアが $ 3 $ 以上になるように $ 3 $ 枚の布を選ぶことはできないため、`2` を出力してください。 ### Sample Explanation 2 与えられた $ 2 $ 枚の布は重なっているので、どの $ 2 $ 枚も重なっていないように $ 2 $ 枚の布を選ぶことはできません。 よって、`-1` を出力してください。 $ 1 $ 枚目の布と $ 2 $ 枚目の布は一点 $ 5 $ でのみ重なっていることに注意してください。 ### Constraints - $ 2\le K\le N\le2\times10 ^ 5 $ - $ 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N) $ - 入力はすべて整数