#include<bits/stdc++.h>
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define LL long long
#define fi first
#define se second
#define eb emplace_back
#define PII pair <int, int>
using namespace std;

const int N = 5e5 + 9;
LL n, K; int q;
vector <pair <LL, int> > seg;
map <LL, int> mp;
void cmax(LL &a, LL b) {if (a < b) a = b;}

LL ans0, ans1;
const LL inf = 1e18;
vector <LL> pos;
struct SegmentTree {
    #define lc (p << 1)
    #define rc (p << 1 | 1)
    LL mx[N << 2], tag1[N << 2], tag2[N << 2];
    void addtag1(int p, LL v) {
        mx[p] += v;
        tag1[p] += v;
        tag2[p] += v;
    }
    void addtag2(int p, LL v) {
        cmax(mx[p], v);
        cmax(tag2[p], v);
    }
    void pushdown(int p) {
        if (tag1[p]) {
            addtag1(lc, tag1[p]);
            addtag1(rc, tag1[p]);
            tag1[p] = 0;
        }
        if (tag2[p]) {
            addtag2(lc, tag2[p]);
            addtag2(rc, tag2[p]);
            tag2[p] = 0;
        }
    }
    void add(int ql, int qr, LL v, int p = 1, int l = 0, int r = pos.size() - 1) {
        if (ql <= l && r <= qr) {
            addtag1(p, v);
            return ;
        }
        if (qr < l || r < ql) return ;
        pushdown(p);
        int mid = (l + r) >> 1;
        add(ql, qr, v, lc, l, mid);
        add(ql, qr, v, rc, mid + 1, r);
        mx[p] = max(mx[lc], mx[rc]);
    }
    void mdf(int ql, int qr, LL v, int p = 1, int l = 0, int r = pos.size() - 1) {
        if (ql <= l && r <= qr) {
            addtag2(p, v);
            return ;
        }
        if (qr < l || r < ql) return ;
        pushdown(p);
        int mid = (l + r) >> 1;
        mdf(ql, qr, v, lc, l, mid);
        mdf(ql, qr, v, rc, mid + 1, r);
        mx[p] = max(mx[lc], mx[rc]);
    }
    LL query(int loc, int p = 1, int l = 0, int r = pos.size() - 1) {
        if (l == r) return mx[p];
        pushdown(p);
        int mid = (l + r) >> 1;
        if (loc <= mid) return query(loc, lc, l, mid);
        return query(loc, rc, mid + 1, r);
    }
} tr;

void fAdd(LL l, LL r, int var) {
    if (r < K) {
        int L = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
        int R = upper_bound(pos.begin(), pos.end(), r) - pos.begin() - 1;
        tr.add(L, R, var);
    }
    else {
        fAdd(l, K - 1, var);
        fAdd(0, r - K, var);
    }
}
void fMax(LL l, LL r, LL var) {
    if (r < K) {
        int L = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
        int R = upper_bound(pos.begin(), pos.end(), r) - pos.begin() - 1;
        tr.mdf(L, R, var);
    }
    else {
        fMax(l, K - 1, var);
        fMax(0, r - K, var);
    }
}

long long play_game(long long N, int Q, long long K, vector<long long> L, vector<long long> R) {
    n = N; q = Q; ::K = K;
    rep (i, 0, q - 1) {
        LL l = L[i], r = R[i];
        ++mp[l];
        --mp[r + 1];
    }
    int sum = 0;
    for (auto p : mp) {
        if (next(mp.find(p.fi)) == mp.end()) break;
        LL l = p.fi, r = next(mp.find(p.fi))->fi - 1;
        sum += p.se;
        LL len = r - l + 1, val = sum;
        ans1 += len / K * val, len %= K;
        if (len == 0) continue;
        seg.eb(len, sum);
    }
    LL cur = 0; pos.eb(cur); 
    for (auto i : seg) {
        LL len = i.fi;
        cur = (cur + len) % K;
        pos.eb(cur);
    }
    sort(pos.begin(), pos.end()); pos.erase(unique(pos.begin(), pos.end()), pos.end());
    // build
    cur = 0;
    for (auto i : seg) {
        LL len = i.fi, val = i.se;
        fAdd(cur + 1, cur + len, val);
        fMax(cur + 1, cur + len, tr.query(lower_bound(pos.begin(), pos.end(), cur) - pos.begin()));
        cur = (cur + len) % K;
    }
    return ans1 + tr.mx[1];
}