まず、答えが \(-1\) かどうかを判定することを考えます。 これは、いわゆる区間スケジューリングの問題になり、次のようなアルゴリズムで解けることが知られています。

1. はじめ、選んだ布の列を空列 \(()\) とする。
2. すべての布を \(R _ i\) の昇順に並べ、順に以下を行う。
   1. 最後に選んだ布 \(\lbrack L _ j, R _ j\rbrack\) に対して \(R _ j\lt L _ i\) が成り立つならば、布 \(\lbrack L _ i,R _ i\rbrack\) を選ぶ。
3. 選ばれた列の長さが \(K\) 未満なら、答えは \(-1\) 。

スコアが \(x\) 以上であるように布を選べるとき、選んだ布の右端から数直線の正の方向に \(x\) 進むまでに他の選んだ布はありません。 よって、スコアが \(x\) 以上であるように布を選べることは以下と同値です。

任意の正の実数 \(\varepsilon\) に対して、それぞれの布が覆う区間を \(\lbrack L _ i,R _ i+x-\varepsilon\rbrack\) とした問題の答えが \(-1\) でない。

これを利用して二分探索でこの問題を解くことができます。

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>

int main() {
    using namespace std;
    unsigned N, K;
    cin >> N >> K;

    vector<pair<unsigned, unsigned>> cloth(N);
    for (auto&& [L, R] : cloth)
        cin >> L >> R;
    
    // 右端でソート
    ranges::sort(cloth, {}, [](const auto& p){return p.second;});

    // 二分探索で布を伸ばせる限界を見つける
    unsigned ans{*ranges::partition_point(views::iota(0U, 1000000000U), [K, &cloth](const unsigned x){
        unsigned chosen{}, last{};
        // 区間スケジューリングで布をなるべく多く選ぶ
        for (const auto& [L, R] : cloth) {
            if (last <= L) {
                ++chosen;
                last = R + x + 1; // 右に x だけ伸ばしておく
            }
        }
        // K 枚以上選べたら OK
        return chosen >= K;
    })};
    
    // 1 以上伸ばせるなら
    if (ans) {
        cout << ans << endl; // それが答え
    } else { // 伸ばせないなら
        cout << -1 << endl; // -1
    }
    return 0;
}