#include <bits/stdc++.h>

using namespace std;
int n, k, l[100005], r[100005];
long long kis=0, nagy=1e9+1, koz;

long long proba(int kezd) {
    int veg=kezd+k-1;
    // a kezd, kezd+1, .... kezd+k-1 helyeket kell lefedni
    long long valasz=0;
    for (int i=1; i<=n; i++) {
        valasz+=max(0, l[i]-kezd);
        valasz+=max(0, veg-r[i]);
    }
    return valasz;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> l[i] >> r[i];
    }

    // "ternary search - konvex kereses" a fuggveny konvex, ezert valameddig monoton csokken utana pedig valameddig monoton no
    // bintaris keresessel konnyu megtalalni, hogy hol valtozik a monotonitas
    while (nagy-kis>1) {
        koz=(nagy+kis)/2;
        if (proba(koz)>proba(koz+1)) {
            kis=koz;
        } else {
            nagy=koz;
        }
    }

    // a ket ertek kozul biztosan az egyik lesz a minimum hely
    cout << min(proba(kis), proba(nagy));
    return 0;
}