#include <algorithm>
#include <climits>
#include <iostream>
#include <functional>
#include <vector>

using namespace std;

using ll = long long;

// lo, hi > 0
template <typename T>
int binary_first_true(T lo, T hi, function<bool(T const&)> const& pred) {
    hi--;

    while (lo < hi) {
        T const mid = (lo + hi) / 2;

        if (pred(mid))
            hi = mid;
        else
            lo = mid + 1;
    }

    return lo;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> s(n);
    vector<int> e(n);

    for (int i = 0; i < n; i++)
        cin >> s[i] >> e[i];

    sort(s.rbegin(), s.rend());
    sort(e.begin(), e.end());


    vector<ll> cost(n + 1);
    cost[0] = LLONG_MAX / 3;
    {
        ll cur = 0;
        ll inc = 0;
        int j = 0;
        for (int i = 1; i <= n + k - 1; i++) {
            while (j < n && e[j] < i) {
                inc++;
                j++;
            }

            cur += inc;
            if (i - k + 1 > 0)
                cost[i - k + 1] += cur;
        }
    }
    {
        ll cur = 0;
        ll inc = 0;
        int j = 0;
        for (int i = n; i > 0; i--) {
            while (j < n && s[j] > i) {
                inc++;
                j++;
            }

            cur += inc;
            cost[i] += cur;
        }
    }

    cout << *min_element(cost.begin(), cost.end()) << "\n";
}